Top Qs
Timeline
Chat
Perspective
Hoffman graph
From Wikipedia, the free encyclopedia
Remove ads
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]
Remove ads
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]
Remove ads
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. Despite not being vertex- or edge-transitive, the Hoffmann graph is still 1-walk-regular (but not distance-regular).
The characteristic polynomial of the Hoffman graph is equal to
making it an integral graph—a graph whose spectrum consists entirely of integers. It is the same spectrum as the hypercube Q4.
Remove ads
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
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads