The Hoffman graph
|Named after||Alan Hoffman|
|Automorphisms||48 (Z/2Z × S4)|
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. Published in 1963, it is cospectral to the hypercube graph Q4.
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.
The characteristic polynomial of the Hoffman graph is equal to
The Hoffman graph is Hamiltonian.
The chromatic number of the Hoffman graph is 2.
The chromatic index of the Hoffman graph is 4.
- Weisstein, Eric W. "Hamiltonian Graph". MathWorld.
- Weisstein, Eric W. "Hoffman graph". MathWorld.
- Hoffman, A. J. "On the Polynomial of a Graph." Amer. Math. Monthly 70, 30-36, 1963.
- van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.
- Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018