Hoffman graph

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 Q 4 . The Hoffman graph has many common properties with the hypercube Q 4 —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 and not 1-planar. It has book thickness 3 and queue number 2.

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 Q 4 . The Hoffman graph has many common properties with the hypercube Q 4 —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 and not 1-planar. It has book thickness 3 and queue number 2. ==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 4 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 (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 as the hypercube Q 4 . ==Gallery== Image:Hoffman graph hamiltonian.svg|The Hoffman graph is Hamiltonian. Image:Hoffman graph 2COL.svg|The chromatic number of the Hoffman graph is 2. Image:Hoffman graph 4color edge.svg|The chromatic index of the Hoffman graph is 4.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1333262690 under CC BY-SA 4.0; modifications have been made.