title: Hoffman graph
text: # 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. 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.
  
  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
  
  * The Hoffman graph is Hamiltonian.
  * The chromatic number of the Hoffman graph is 2.
  * The chromatic index of the Hoffman graph is 4.
  