Hoffman graph

Hoffman graph
The Hoffman graph
Named after	Alan Hoffman
Vertices	16
Edges	32
Radius	3
Diameter	4
Girth	4
Automorphisms	48 (Z/2Z × S4)
Chromatic number	2
Chromatic index	4
Properties	Hamiltonian[1] Bipartite Perfect Eulerian

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 Q₄.^[3][4]

The Hoffman graph has many common properties with the hypercube Q₄—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.

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 S₄ and the cyclic group Z/2Z.

The characteristic polynomial of the Hoffman graph is equal to

$(x-4) (x-2)^4 x^6 (x+2)^4 (x+4)$

making it an integral graph—a graph whose spectrum consists entirely of integers. It is the same spectrum than the hypercube Q₄.

Gallery

• 

  The Hoffman graph is Hamiltonian.

• 

  The chromatic number of the Hoffman graph is 2.

• 

  The chromatic index of the Hoffman graph is 4.

References

1. Weisstein, Eric W., "Hamiltonian Graph", MathWorld.
2. Weisstein, Eric W., "Hoffman graph", MathWorld.
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.