Holt graph
<templatestyles src="Infobox graph/styles.css"/>Script error: No such module "Infobox". 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.[1][2] Such graphs are not common.[3] It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976[4] and 1981[5] respectively.
The Holt graph has diameter 3, radius 3 and girth 5, chromatic number 3, chromatic index 5 and is Hamiltonian with 98,472 distinct Hamiltonian cycles.[6] It is also a 4-vertex-connected and a 4-edge-connected graph. It has book thickness 3 and queue number 3.[7]
It has an automorphism group of order 54.[6] 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
Gallery
-
The chromatic number of the Holt graph is 3.
-
The chromatic index of the Holt graph is 5.
-
The Holt graph is Hamiltonian.
-
The Holt graph is a unit distance graph.
References
<templatestyles src="Reflist/styles.css" />
- ↑ Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. [1]
- ↑ Script error: No such module "citation/CS1"..
- ↑ Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory, CRC Press, 2004, Template:ISBN, p. 491.
- ↑ Script error: No such module "citation/CS1".. As cited by MathWorld.
- ↑ Script error: No such module "citation/CS1"..
- ↑ a b Script error: No such module "Template wrapper".
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
Script error: No such module "Check for unknown parameters".