From Surf Wiki (app.surf) — the open knowledge base
Holt graph
| Field | Value | |
|---|---|---|
| name | Holt graph | |
| image | [[File:HoltGraph.svg | 220px]] |
| image_caption | In the Holt graph, all vertices are equivalent, and all edges are equivalent, but edges are not equivalent to their inverses. | |
| namesake | Derek F. Holt | |
| vertices | 27 | |
| edges | 54 | |
| automorphisms | 54 | |
| girth | 5 | |
| diameter | 3 | |
| radius | 3 | |
| chromatic_number | 3 | |
| chromatic_index | 5 | |
| properties | Vertex-transitive | |
| Edge-transitive | ||
| Half-transitive | ||
| Hamiltonian | ||
| Eulerian | ||
| Cayley graph | ||
| book thickness | 3 | queue number=3 |
Edge-transitive Half-transitive Hamiltonian Eulerian Cayley graph In graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric. Such graphs are not common. It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976 and 1981 respectively.
The Holt graph has diameter 3, radius 3 and girth 5, chromatic number 3, chromatic index 5 and is Hamiltonian with distinct Hamiltonian cycles. It is also a 4-vertex-connected and a 4-edge-connected graph. It has book thickness 3 and queue number 3.
It has an automorphism group of order 54. This is a smaller group than a symmetric graph with the same number of vertices and edges would have. The graph drawing on the right highlights this, in that it lacks reflectional symmetry.
The characteristic polynomial of the Holt graph is :(x^3-6x+2)^6(x+2)^4(x-1)^4(x-4).\
Gallery
Image:Holt graph 3COL.svg|The chromatic number of the Holt graph is 3. Image:Holt graph 5color edge.svg|The chromatic index of the Holt graph is 5. Image:Holt graph hamiltonian.svg|The Holt graph is Hamiltonian. File:Holt graph unit distance.svg|The Holt graph is a unit distance graph.
References
References
- Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. [https://arxiv.org/abs/math/0703861/]
- (1994). "Constructing Graphs which are ½-Transitive". [[Journal of the Australian Mathematical Society, Series A]].
- Jonathan L. Gross, Jay Yellen, ''Handbook of Graph Theory'', CRC Press, 2004, {{ISBN. 1-58488-090-2, p. 491.
- Doyle, P. G.. (1976). "On Transitive Graphs". Harvard College.
- Holt, Derek F.. (1981). "A graph which is edge transitive but not arc transitive". [[Journal of Graph Theory]].
- "Doyle Graph".
- Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018
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 Holt 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