Integral Graph


An integral graph, not to be confused with an integral embedding of a graph, is defined as 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 0, 2, 3, 6, 10, 20, 33, 71, ... (OEIS A077027), illustrated above for small n.


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.

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

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

See also

Eigenvalue, Graph Spectrum, Unit-Distance Graph

Explore with Wolfram|Alpha


Harary, F. and Schwenk, A. J. "Which Graphs have Integral Spectra?" In Graphs and Combinatorics (Ed. R. Bari and F. Harary). Berlin: Springer-Verlag, pp. 45-51, 1974.Sloane, N. J. A. Sequences 064731 A 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 Web Resource.

Subject classifications