Holt graph
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. The graph is not 1-planar. 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).\
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. The graph is not 1-planar. 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1337474504 under CC BY-SA 4.0; modifications have been made.