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 (relatifs). 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.

Le graphe de Petersen est un graphe intégral de spectre $(3,1,1,1,1,1,-2,-2,-2,-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.

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.