# Robertson graph

In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4-regular undirected graph with 19 vertices and 38 edges named after Neil Robertson.

Robertson graph The Robertson graph is Hamiltonian.
Named afterNeil Robertson
Vertices19
Edges38
Diameter3
Girth5
Automorphisms24 (D12)
Chromatic number3
Chromatic index5
Book thickness3
Queue number2
PropertiesCage
Hamiltonian
Table of graphs and parameters

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 3, chromatic index 5, diameter 3, radius 3 and is both 4-vertex-connected and 4-edge-connected. It has book thickness 3 and queue number 2.

The Robertson graph is also a Hamiltonian graph which possesses 5,376 distinct directed Hamiltonian cycles.

## Algebraic properties

The Robertson graph is not a vertex-transitive graph and its full automorphism group is isomorphic to the dihedral group of order 24, the group of symmetries of a regular dodecagon, including both rotations and reflections.

The characteristic polynomial 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).\$