Holt graph

Holt graph
In the Holt graph, all vertices are equivalent, and all edges are equivalent, but edges are not necessarily equivalent to their inverses.
Named after	Derek F. Holt
Vertices	27
Edges	54
Radius	3
Diameter	3
Girth	5
Automorphisms	54
Chromatic number	3
Chromatic index	5
Properties	Vertex-transitive Edge-transitive Half-transitive Hamiltonian Eulerian Cayley graph

In the mathematical field of 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 98,472 distinct Hamiltonian cycles. It is also a 4-vertex-connected and a 4-edge-connected graph.

It has an automorphism group of order 54 automorphisms. 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

• Holt graph 3COL.svg

  The chromatic number of the Holt graph is 3.

• Holt graph 5color edge.svg

  The chromatic index of the Holt graph is 5.

• Holt graph hamiltonian.svg

  The Holt graph is Hamiltonian.