In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the Robertson graph or (4,5)-cage, is a 4- regular

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

with 19 vertices and 38 edges named after

Neil Robertson Neil Robertson (born 11 February 1982) is an Australian professional snooker player who is a former world champion and former world number one. The only Australian to have won a ranking event, he is also the only player from outside the United ...

. The Robertson graph is the unique (4,5)-cage graph and was discovered by Robertson in 1964. As a cage graph, it is the smallest 4-regular graph with girth 5. It has

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...

5, diameter 3, radius 3 and is both 4- vertex-connected and 4- edge-connected. It has

book thickness In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie o ...

3 and

queue number In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Defin ...

2.Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018 The Robertson graph is also a

Hamiltonian graph In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

which possesses distinct directed Hamiltonian cycles. The Robertson graph is one of the smallest graphs with

cop number In graph theory, a branch of mathematics, the cop number or copnumber of an undirected graph is the minimum number of cops that suffices to ensure a win (i.e., a capture of the robber) in a certain pursuit–evasion game on the graph. Rules In th ...

4.Turcotte, J., & Yvon, S. (2021). 4-cop-win graphs have at least 19 vertices. Discrete Applied Mathematics, 301, 74-98.

Algebraic properties

The Robertson graph is not a

vertex-transitive graph In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive i ...

and its full automorphism group is isomorphic to the

dihedral group In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...

of order 24, the group of symmetries of a regular

dodecagon In geometry, a dodecagon or 12-gon is any twelve-sided polygon. Regular dodecagon A regular dodecagon is a figure with sides of the same length and internal angles of the same size. It has twelve lines of reflective symmetry and rotational sym ...

, including both rotations and reflections.Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15, 2008. The

characteristic polynomial In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The chara ...

of the Robertson graph is :

(x-4)(x-1)^2(x^2-3)^2(x^2+x-5)

(x^2+x-4)^2(x^2+x-3)^2(x^2+x-1).\

Gallery

Image:Robertson graph.svg, The Robertson graph as drawn in the original publication. Image:Robertson graph 3COL.svg, The

of the Robertson graph is 3. Image:Robertson graph 5color edge.svg, The

of the Robertson graph is 5.

References

{{reflist Individual graphs Regular graphs