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.[2] Published in 1963, it is cospectral to the hypercube graph Q4.[3][4]

Hoffman graph
The Hoffman graph
Named afterAlan Hoffman
Vertices16
Edges32
Radius3
Diameter4
Girth4
Automorphisms48 (Z/2Z × S4)
Chromatic number2
Chromatic index4
Book thickness3
Queue number2
PropertiesHamiltonian[1]
Bipartite
Perfect
Eulerian
Table of graphs and parameters

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]

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.

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.

  • The Hoffman graph is Hamiltonian.
  • The chromatic number of the Hoffman graph is 2.
  • The chromatic index of the Hoffman graph is 4.
gollark: Although I think part of the issue is that HTML/CSS is actually a reasonably nice cross-platform environment to write against, in a way not really matched by anything else with the same ubiquity.
gollark: Yes. I can, happily, mostly just run them in my browser.
gollark: I use Void Linux for purposes, I find it much nicer than Raspbian. Also more lightweight.
gollark: Perhaps it has some sort of connection tracking limit.
gollark: Not unsafe in the sense that it'll do undefined behaviour probably, just that you can't statically be sure it only contains the type you want.

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.
  5. Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.