Integral graph

The blue graph, C₄, is one of the only integral cycle graphs, whose adjacency matrix has eigenvalues ${\displaystyle 0,0,2,-2}$. The red graph is not integral, as its eigenvalues are ${\displaystyle 0,-1,{\frac {{\sqrt {17}}+1}{2}},{\frac {-{\sqrt {17}}+1}{2}}}$.

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 Frank Harary and Allen Schwenk. ^[2]

Examples

• The complete graph K_n is integral for all n. ^[2]
• The only cycle graphs that are integral are ${\displaystyle C_{3}}$, ${\displaystyle C_{4}}$, and ${\displaystyle C_{6}}$. ^[2]
• If a graph is integral, then so is its complement graph; for instance, the complements of complete graphs, edgeless graphs, are integral. If two graphs are integral, then so is their Cartesian product and strong product; ^[2] for instance, the Cartesian products of two complete graphs, the rook's graphs, are integral. ^[3] Similarly, the hypercube graphs, as Cartesian products of any number of complete graphs ${\displaystyle K_{2}}$, are integral. ^[2]
• The line graph of an integral graph is again integral. For instance, as the line graph of ${\displaystyle K_{4}}$, the octahedral graph is integral, and as the complement of the line graph of ${\displaystyle K_{5}}$, the Petersen graph is integral. ^[2]
• 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. ^[4]

References

1. Weisstein, Eric W., "Integral Graph", MathWorld
2. Harary, Frank; Schwenk, Allen J. (1974), "Which graphs have integral spectra?", in Bari, Ruth A.; Harary, Frank (eds.), Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University, Washington, D.C., June 18–22, 1973, Lecture Notes in Mathematics, vol. 406, Springer, pp. 45–51, doi:10.1007/BFb0066434, MR   0387124
3. Doob, Michael (1970), "On characterizing certain graphs with four eigenvalues by their spectra", Linear Algebra and its Applications , 3: 461–482, doi: 10.1016/0024-3795(70)90037-6 , MR   0285432
4. Sander, Torsten (2009), "Sudoku graphs are integral", Electronic Journal of Combinatorics, 16 (1): Note 25, 7, MR   2529816