Holt 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.[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.

Holt graph
In the Holt graph, all vertices are equivalent, and all edges are equivalent, but edges are not equivalent to their inverses.
Named afterDerek F. Holt
Vertices27
Edges54
Radius3
Diameter3
Girth5
Automorphisms54
Chromatic number3
Chromatic index5
Book thickness3
Queue number3
PropertiesVertex-transitive
Edge-transitive
Half-transitive
Hamiltonian
Eulerian
Cayley graph
Table of graphs and parameters

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 automorphisms.[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

  • The chromatic number of the Holt graph is 3.
  • The chromatic index of the Holt graph is 5.
  • The Holt graph is Hamiltonian.
gollark: In general, yes.
gollark: http://sam.zeloof.xyz/first-ic/
gollark: I mean, unless you don't mind artisanal handmade 100μm transistors.
gollark: You *can* just buy a desktop computer of some kind as a decent substitute, there's much more choice there, but not (unlike in phones) extra ethical™ computer parts.
gollark: Oh, so NOT supply chains but just "there aren't replacements for all things".

References
  1. Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998.
  2. Alspach, Brian; Marušič, Dragan; Nowitz, Lewis (1994), "Constructing Graphs which are ½-Transitive", Journal of the Australian Mathematical Society Series A, 56 (3): 391–402, doi:10.1017/S1446788700035564, archived from the original on 2003-11-27.
  3. Jonathan L. Gross, Jay Yellen, Handbook of Graph Theory, CRC Press, 2004, ISBN 1-58488-090-2, p. 491.
  4. Doyle, P. G. (1976), On Transitive Graphs, Senior Thesis, Harvard College. As cited by MathWorld.
  5. Holt, Derek F. (1981), "A graph which is edge transitive but not arc transitive", Journal of Graph Theory, 5 (2): 201–204, doi:10.1002/jgt.3190050210.
  6. Weisstein, Eric W. "Doyle Graph". MathWorld.
  7. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.