Grafo integral

No campo da matemática da teoria dos grafos, um grafo integral é um grafo cujo espectro consiste inteiramente de inteiros. Em outras palavras, um grafo é um grafo integral, se todos os autovalores dos seus polinômios característicos são inteiros.

O conceito foi introduzido em 1974 por Harary e Schwenk.^[1]

Exemplos

• O grafo completo K_n é integral para todo n.
• O grafo sem arestas ${\displaystyle {\bar {K}}_{n}}$ é integral para todo n.
• Entre os grafos cubicos simétricos, o grafo utilitário, o grafo de Petersen, o grafo de Nauru e o grafo de Desargues são integrais.
• O grafo de Higman–Sims, o grafo de Hall–Janko, o grafo de Clebsch, o grafo de Hoffman–Singleton, o grafo de Shrikhande e o grafo de Hoffman são integrais.

Referências

1. 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.