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

• The complete graph K_n is integral for all n.^[2]
• The only cycle graphs that are integral are C 3 {\displaystyle C_{3}} , C 4 {\displaystyle C_{4}} , and C 6 {\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 K 2 {\displaystyle 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 {\displaystyle K_{4}} , the octahedral graph is integral, and as the complement of the line graph of K 5 {\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]