Holt graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Provenance

snapshot enwiki-001337474504 · captured 1770657402.0 · version history

Cite this page as: encyclopegia.org, “Holt graph”, snapshot enwiki-001337474504. https://encyclopegia.org/a/holt-graph

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.