Integral graph

In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjacency matrix 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 ${\displaystyle {\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.
• A regular graph is periodic if and only if it is an integral graph.
• A walk-regular graph that admits perfect state transfer is an integral graph.
• The Sudoku graphs, graphs whose vertices represent cells of a Sudoku board and whose edges represent cells that should not be equal, are integral.[3]

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.
3. Sander, Torsten (2009), "Sudoku graphs are integral", Electronic Journal of Combinatorics, 16 (1): Note 25, 7, MR 2529816