From Surf Wiki (app.surf) — the open knowledge base
Robertson graph
| Field | Value | |
|---|---|---|
| name | Robertson graph | |
| image | [[Image:Robertson graph hamiltonian.svg | 240px]] |
| image_caption | The Robertson graph is Hamiltonian. | |
| namesake | Neil Robertson | |
| vertices | 19 | |
| edges | 38 | |
| automorphisms | 24 (D12) | |
| girth | 5 | |
| diameter | 3 | |
| radius | 3 | |
| chromatic_number | 3 | |
| chromatic_index | 5 | |
| properties | Cage | |
| Hamiltonian | ||
| book thickness | 3 | queue number=2 |
Hamiltonian 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.
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 graph is neither planar nor 1-planar.{{citation | editor-first1 = Vida | editor-last1 = Dujmović | editor-first2 = Fabrizio | editor-last2 = Montecchiani
The Robertson graph is also a Hamiltonian graph which possesses distinct directed Hamiltonian cycles.
The Robertson graph is one of the smallest graphs with cop number 4.
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.
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).\
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.
References
References
- "Class 2 Graph".
- "Robertson Graph".
- Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.
- Robertson, N. "The Smallest Graph of Girth 5 and Valency 4." Bull. Amer. Math. Soc. 70, 824-825, 1964.
- Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018
- Turcotte, J., & Yvon, S. (2021). 4-cop-win graphs have at least 19 vertices. Discrete Applied Mathematics, 301, 74-98.
- Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15, 2008.
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Robertson graph — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report