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 , 2, ... nodes are 0, 2, 3, 6, 10, 20, 33, 71, ... (OEIS A077027), illustrated above for small .

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

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

graph	integral for  of the form
antiprism graph	3
complete graph	all
cycle graph	2, 3, 4, 6
empty graph	all
prism graph	3, 4, 6
star graph
wheel graph	4

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

graph	graph spectrum
16-cell
24-cell
Clebsch graph
cubical graph
cuboctahedral graph
Desargues graph
Hall-Janko graph
Hoffman graph
Hoffman-Singleton graph
Levi graph
M22 graph
McLaughlin graph
octahedral graph
pentatope
Petersen graph
Shrikhande graph
-simplex
small triakis octahedral graph
Sylvester graph
tesseract
tetrahedral graph
truncated tetrahedral graph
utility graph

REFERENCES

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."