Hoffman graph

From HandWiki
Hoffman graph
Hoffman graph.svg
The Hoffman graph
Named afterAlan Hoffman
Vertices16
Edges32
Radius3
Diameter4
Girth4
Automorphisms48 (Z/2Z × S4)
Chromatic number2
Chromatic index4
Book thickness3
Queue number2
PropertiesHamiltonian[1]
Bipartite
Perfect
Eulerian
Table of graphs and parameters

In the mathematical field of graph theory, the Hoffman graph is a 4-regular graph with 16 vertices and 32 edges discovered by Alan Hoffman.[2] Published in 1963, it is cospectral to the hypercube graph Q4.[3][4]

The Hoffman graph has many common properties with the hypercube Q4—both are Hamiltonian and have chromatic number 2, chromatic index 4, girth 4 and diameter 4. It is also a 4-vertex-connected graph and a 4-edge-connected graph. However, it is not distance-regular. It has book thickness 3 and queue number 2.[5]

Algebraic properties

The Hoffman graph is not a vertex-transitive graph and its full automorphism group is a group of order 48 isomorphic to the direct product of the symmetric group S4 and the cyclic group Z/2Z.

The characteristic polynomial of the Hoffman graph is equal to

[math]\displaystyle{ (x-4) (x-2)^4 x^6 (x+2)^4 (x+4) }[/math]

making it an integral graph—a graph whose spectrum consists entirely of integers. It is the same spectrum as the hypercube Q4.

Gallery

References

  1. Weisstein, Eric W.. "Hamiltonian Graph". http://mathworld.wolfram.com/HamiltonianGraph.html. 
  2. Weisstein, Eric W.. "Hoffman graph". http://mathworld.wolfram.com/HoffmanGraph.html. 
  3. Hoffman, A. J. "On the Polynomial of a Graph." Amer. Math. Monthly 70, 30-36, 1963.
  4. van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.
  5. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018