TOPICS
Search

Hoffman Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HoffmanGraph

The Hoffman graph is the bipartite graph on 16 nodes and 32 edges illustrated above that is cospectral to the tesseract graph Q_4 (Hoffman 1963, van Dam and Haemers 2003). Q_4 and the Hoffman graph are therefore not determined by their spectrum. Its girth, graph diameter, graph spectrum, and characteristic polynomial are the same as those of Q_4, but its graph radius is 3 compared to the value 4 for Q_4.

The Hoffman graph has adjacency matrix given by

A=[0 D; D^T 0],

where D^(T) denotes the transpose and D is defined by

D=[1 1 1 1 0 0 0 0; 1 1 1 0 1 0 0 0; 1 0 0 1 0 1 1 0; 0 1 0 1 0 1 0 1; 0 0 1 1 0 0 1 1; 1 0 0 0 1 1 1 0; 0 1 0 0 1 1 0 1; 0 0 1 0 1 0 1 1].

The Hoffman graph is an integral graph with graph spectrum (-4)^1(-2)^40^62^44^1.

It is the smallest known conformally rigid graph that is not edge-transitive or distance-regular (Steinerberger and Thomas 2024).

See also

Cospectral Graphs, Determined by Spectrum, Hoffman-Singleton Graph, Integral Graph, Tesseract Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, p. 263, 1989.Hoffman, A. J. "On the Polynomial of a Graph." Amer. Math. Monthly 70, 30-36, 1963.Steinerberger, S. and Thomas, R. R. "Conformally Rigid Graphs." 19 Feb 2024. https://arxiv.org/abs/2402.11758.van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

Referenced on Wolfram|Alpha

Hoffman Graph

Cite this as:

Weisstein, Eric W. "Hoffman Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HoffmanGraph.html

Subject classifications