From Surf Wiki (app.surf) — the open knowledge base
Hoffman graph
| Field | Value | |
|---|---|---|
| name | Hoffman graph | |
| image | [[Image:Hoffman graph.svg | 220px]] |
| image_caption | The Hoffman graph | |
| namesake | Alan Hoffman | |
| vertices | 16 | |
| edges | 32 | |
| automorphisms | 48 (Z/2Z × S4) | |
| girth | 4 | |
| diameter | 4 | |
| radius | 3 | |
| chromatic_number | 2 | |
| chromatic_index | 4 | |
| properties | Hamiltonian | |
| Bipartite | ||
| Perfect | ||
| Eulerian | ||
| 1-walk regular | ||
| book thickness | 3 | queue number=2 |
Bipartite Perfect Eulerian 1-walk regular
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 and not 1-planar.{{citation | editor-first1 = Vida | editor-last1 = Dujmović | editor-first2 = Fabrizio | editor-last2 = Montecchiani 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 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 :(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 Q4.
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.
References
References
- "Hamiltonian Graph".
- "Hoffman graph".
- 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
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Hoffman graph — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report