Integral graph

In the mathematical field of graph theory, an integral graph is a graph whose spectrum consists entirely of integers. In other words, a graphs is an integral graph if all the eigenvalues of its characteristic polynomial are integers.^[1]

The notion was introduced in 1974 by Harary and Schwenk.^[2]

Examples

• The complete graph K_n is integral for all n.
• The edgeless graph $\bar K_n$ is integral for all n.
• Among the cubic symmetric graphs the utility graph, the Petersen graph, the Nauru graph and the Desargues graph are integral.
• The Higman–Sims graph, the Hall–Janko graph, the Clebsch graph, the Hoffman–Singleton graph, the Shrikhande graph and the Hoffman graph are integral.

References

1. Weisstein, Eric W., "Integral Graph", MathWorld.
2. 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.