Graphe intégral

Le graphe de Petersen est un graphe intégral de spectre ${\displaystyle (3,1,1,1,1,1,-2,-2,-2,-2)}$.

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 (relatifs)^[1]. En d'autres termes, les racines de son polynôme caractéristique sont toutes entières. Leur étude fut introduite par Harary et Schwenk en 1974^[2].

Graphes intégraux à peu de sommets

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

Graphes intégraux remarquables

De nombreux graphes remarquables sont intégraux comme les hypercubes et les graphes complets. On peut aussi citer le cas du graphe hexaédrique, du graphe octaédrique, du graphe dodécaédrique, du graphe icosaédrique, du graphe cuboctaédrique, du graphe tétraédrique tronqué, du graphe triakioctaédrique, ainsi que du graphe de Clebsch, du graphe de Desargues, du graphe de Hall-Janko, du graphe de Higman-Sims, du graphe de Hoffman, du graphe de Hoffman-Singleton, du graphe de Kummer, du graphe M22, du graphe de McLaughlin et du graphe local de McLaughlin, du graphe de Nauru, du graphe de Petersen, du graphe de Schläfli, du graphe de Shrikhande, du graphe de Suzuki, du graphe de Sylvester, du graphe tronqué de Witt et du graphe de Tutte–Coxeter, ainsi que des produits d'un ensemble fini quelconque de ces graphes.

Références

1. (en) Eric W. Weisstein, « Integral Graph », sur MathWorld
2. (en) F. Harary et A. J. Schwenk, « Which Graphs have Integral Spectra? », dans R. Bari et F. Harary, Graphs and Combinatorics, Berlin, Springer, 1974, p. 45-51
3. (en) Number of connected integral graphs on n vertices : suite A064731 de l'OEIS