TOPICS
Search

Hoffman Graph


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.

Cite this as:

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

Subject classifications