Graphe intégral

En théorie des graphes, un graphe intégral est un graphe dont le spectre de la matrice d'adjacence ne contient que des entiers^[1]. En d'autres termes, les racines de son polynôme caractéristiques sont toutes entières. Leur étude fut introduite par Harary et Schwenk en 1974^[2].

Exemples

Le plus petit graphe intégral est le graphe singleton.

Aux ordres 1, 2 et 3 il existe un unique graphe connexe intégral. Il existe 2 graphes connexes intégraux distincts à isomorphisme près à l'ordre 4, 3 à l'ordre 5, 6 à l'ordre 6, 7 à l'ordre 7, 22 à l'ordre 8, 24 à l'ordre 9 et 83 à l'ordre 10^[3].

Parmi les graphes célèbres certains sont intégraux. C'est le cas du graphe hexaédrique, du graphe octaédrique, du graphe cuboctaédrique, du graphe tétraédrique, du graphe tétraédrique tronqué, du graphe de Petersen, du graphe de Desargues, du graphe de Nauru, du graphe de Hall-Janko, du graphe de Hoffman, du graphe de Hoffman-Singleton, du graphe de Tutte–Coxeter, du graphe de McLaughlin, du graphe de Clebsch, du graphe de Shrikhande, du graphe de Sylvester, du graphe tesseract et du graphe M22.

Références

1. ↑ (en) Eric W. Weisstein, Integral Graph (MathWorld)
2. ↑ (en) 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.
3. ↑ (en) N. J. A. Sloane Number of connected integral graphs on n vertices. . The On-Line Encyclopedia of Integer Sequences (id:A064731 ).