TOPICS
Search

Integral Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
IntegralGraphs

An integral graph, not to be confused with an integral drawing of a graph, is a graph whose graph spectrum consists entirely of integers. The notion was first introduced by Harary and Schwenk (1974). The numbers of simple integral graphs on n=1, 2, ... nodes are 1, 2, 3, 6, 10, 20, 33, 71, ... (OEIS A077027), illustrated above for small n.

IntegralConnectedGraphs

The numbers of connected simple integral graphs on n=1, 2, ... nodes are 1, 1, 1, 2, 3, 6, 7, 22, 24, 83, ... (OEIS A064731), illustrated above for small n.

Braga et al. (2026a) proved that every simple graph having a pendant path with at least three edges has a graph eigenvalue in (1,2cos(pi/9)] and another in [-2cos(pi/9),-1). Consequently, every such graph is nonintegral. The positive interval is best possible for real symmetric matrices with such a terminal path; sharpness for adjacency matrices of simple graphs is not asserted (Gladkikh and Solovyev 2026).

The following table lists common graph classes and their members which are integral.

graphintegral for n of the form
antiprism graph3
complete graph K_nall
cycle graph C_n2, 3, 4, 6
empty graphall
prism graph3, 4, 6
star graph S_nn^2+1
wheel graph W_n4

The following table lists some special named graphs that are integral and gives their spectra.

graphgraph spectrum
16-cell(-2)^30^46^1
24-cell graph(-4)^2(-2)^80^94^48^1
Clebsch graph(-3)^51^(10)5^1
cubical graph(-3)^1(-1)^31^33^1
cuboctahedral graph(-2)^50^32^34^1
Desargues graph(-3)^1(-2)^4(-1)^51^52^43^1
Hall-Janko graph(-4)^(63)6^(36)36^1
Hoffman graph(-4)^1(-2)^40^62^44^1
Hoffman-Singleton graph(-3)^(21)2^(28)7^1
Tutte 8-cage(-3)^1(-2)^90^(10)2^93^1
M22 graph(-6)^(21)2^(55)16^1
McLaughlin graph(-28)^(22)2^(252)112^1
octahedral graph(-2)^20^34^1
pentatope(-1)^44^1
Petersen graph(-2)^41^53^1
Shrikhande graph(-2)^92^66^1
n-simplex(-1)^nn^1
small triakis octahedral graph(-2)^60^42^36^1
Sylvester graph(-3)^9(-1)^(10)5^12^(16)
tesseract(-4)^1(-2)^40^62^44^1
tetrahedral graph(-1)^33^1
truncated tetrahedral graph(-2)^3(-1)^30^22^33^1
utility graph(-3)^10^43^1

Among connected unicyclic graphs, the triangle graph C_3 is the only nonbipartite integral graph (Braga et al. 2026b). Braga et al. (2026b) acknowledge Claude assistance with exploring ideas and checking proofs, and state that they verified the mathematical content.

See also

Eigenvalue, Graph Spectrum, Unicyclic Graph, Unit-Distance Graph

Explore with Wolfram|Alpha

References

Braga, R. O.; Moraes, J. C.; and Santos, M. C. "Pendant Paths and Integral Generalized Sun Graphs." 23 Sep 2026a. https://arxiv.org/abs/2609.28754.Braga, R. O.; Moraes, J. C.; and Santos, M. C. "Spectral Asymmetry and Odd Cycles in Integral Graphs." 16 Oct 2026b. https://arxiv.org/abs/2610.22773.Harary, F. and Schwenk, A. J. "Which Graphs Have Integral Spectra?" In Graphs and Combinatorics (Ed. R. Bari and F. Harary). Berlin, Germany: Springer-Verlag, pp. 45-51, 1974.Sloane, N. J. A. Sequences A064731 and A077027 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Integral Graph

Cite this as:

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

Subject classifications