integral graph

File:Integral and Non-Integral graphs.svg, is one of the only integral cycle graphs, whose adjacency matrix has eigenvalues $0, 0, 2, -2$ . The red graph is not integral, as its eigenvalues are $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.{{MathWorld|urlname=IntegralGraph|title=Integral Graph|mode=cs2}}

The notion was introduced in 1974 by Frank Harary and Allen Schwenk.{{citation

| last1 = Harary | first1 = Frank | author1-link = Frank Harary

| last2 = Schwenk | first2 = Allen J.

| editor1-last = Bari | editor1-first = Ruth A. | editor1-link = Ruth Aaronson Bari

| editor2-last = Harary | editor2-first = Frank

| contribution = Which graphs have integral spectra?

| doi = 10.1007/BFb0066434

| mr = 0387124

| pages = 45–51

| publisher = Springer

| series = Lecture Notes in Mathematics

| title = 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

| volume = 406

| year = 1974}}

Examples

The complete graph K_n is integral for all n.
The only cycle graphs that are integral are $C_3$ , $C_4$ , and $C_6$ .
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; for instance, the Cartesian products of two complete graphs, the rook's graphs, are integral.{{citation

| last = Doob | first = Michael

| doi = 10.1016/0024-3795(70)90037-6

| journal = Linear Algebra and its Applications

| mr = 285432

| pages = 461–482

| title = On characterizing certain graphs with four eigenvalues by their spectra

| volume = 3

| year = 1970| doi-access = free

}} Similarly, the hypercube graphs, as Cartesian products of any number of complete graphs $K_2$ , are integral.

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 of $K_5$ , the Petersen graph is integral.
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.{{citation

| last = Sander | first = Torsten

| issue = 1

| journal = Electronic Journal of Combinatorics

| mr = 2529816

| page = Note 25, 7

| title = Sudoku graphs are integral

| url = https://www.combinatorics.org/Volume_16/Abstracts/v16i1n25.html

| volume = 16

| year = 2009}}

References

Category:Graph families

Category:Algebraic graph theory