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 Kn is integral for all n.[2]
- The only cycle graphs that are integral are
C_3,C_4, andC_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
K_2, are integral.[2] - The line graph of a regular integral graph is again integral. For instance, as the line graph of
K_4, the octahedral graph is integral, and as the complement of the line graph ofK_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
- ^
- ^ Harary, Frank & Schwenk, Allen J. (1974), "Which graphs have integral spectra?", 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, Vol. 406, Lecture Notes in Mathematics, Springer, pp. 45–51, doi:10.1007/BFb0066434. ISBN 978-3-540-06854-9. MR 0387124
- ^ Doob, Michael (1970), "On characterizing certain graphs with four eigenvalues by their spectra", Linear Algebra and Its Applications. 3 (4): 461–482, doi:10.1016/0024-3795(70)90037-6. MR 285432
- ^ Sander, Torsten (2009), "Sudoku graphs are integral", Electronic Journal of Combinatorics. 16 (1): Note 25, 7, doi:10.37236/263. MR 2529816