{{infobox graph | name = Robertson graph | image = 240px | image_caption = The Robertson graph is Hamiltonian. | namesake = Neil Robertson | vertices = 19 | edges = 38 | automorphisms = 24 (D<sub>12</sub>) | girth = 5 | diameter = 3 | radius = 3 | chromatic_number = 3 | chromatic_index = 5<ref>{{MathWorld|urlname=Class2Graph|title=Class 2 Graph}}</ref> | properties = Cage<br>Hamiltonian |book thickness=3|queue number=2}} 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.<ref>{{MathWorld|urlname=RobertsonGraph|title=Robertson Graph}}</ref><ref>Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.</ref>
The Robertson graph is the unique (4,5)-cage graph and was discovered by Robertson in 1964.<ref>Robertson, N. "The Smallest Graph of Girth 5 and Valency 4." Bull. Amer. Math. Soc. 70, 824-825, 1964.</ref> 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.<ref>Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018</ref> The graph is neither planar nor 1-planar.<ref>{{citation | last = Pupyrev | first = Sergey | editor-first1 = Vida | editor-last1 = Dujmović | editor-first2 = Fabrizio | editor-last2 = Montecchiani | contribution = OOPS: Optimized One-Planarity Solver via SAT | title = Proc. 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) | series = Leibniz International Proceedings in Informatics (LIPIcs) | year = 2025 | volume = 357 | pages = 14:1–14:19 | doi = 10.4230/LIPIcs.GD.2025.14 | isbn = 978-3-95977-403-1 | doi-access = free }}.</ref>
The Robertson graph is also a Hamiltonian graph which possesses {{formatnum:5376}} distinct directed Hamiltonian cycles.
The Robertson graph is one of the smallest graphs with cop number 4.<ref name="ROB4">Turcotte, J., & Yvon, S. (2021). 4-cop-win graphs have at least 19 vertices. Discrete Applied Mathematics, 301, 74-98.</ref>
==Algebraic properties== The Robertson graph is not a vertex-transitive graph; 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.<ref name="SURV">Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15, 2008.</ref>
The characteristic polynomial of the Robertson graph is :<math>(x-4)(x-1)^2(x^2-3)^2(x^2+x-5)</math> :<math>(x^2+x-4)^2(x^2+x-3)^2(x^2+x-1).\ </math>
==Gallery== <gallery> Image:Robertson graph.svg|The Robertson graph as drawn in the original publication. Image:Robertson graph 3COL.svg|The chromatic number of the Robertson graph is 3. Image:Robertson graph 5color edge.svg|The chromatic index of the Robertson graph is 5. </gallery>
== References == {{reflist}}
Category:Individual graphs Category:Regular graphs