Graphe intégral

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe intégral de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Graphe de Nauru — Représentation du graphe de Nauru. Notation F24A Nombre de sommets 24 Nombre d arêtes 36 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe de Hoffman-Singleton — Schéma du graphe de Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés …   Wikipédia en Français

  • Graphe D'Hoffman-Singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 …   Wikipédia en Français

  • Graphe d'Hoffman-Singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 …   Wikipédia en Français

  • Graphe d'hoffman-singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 …   Wikipédia en Français

  • Graphe de Clebsch — Représentation du graphe de Clebsch Nombre de sommets 16 Nombre d arêtes 40 Distribution des degrés 5 régulier Rayon …   Wikipédia en Français

  • Graphe tesseract — Une représentation du graphe tesseract. Nombre de sommets 16 Nombre d arêtes 32 Distribution des degrés 4 régulier Rayon 4 …   Wikipédia en Français

  • Graphe tétraédrique — Représentation du graphe tétraédrique. Nombre de sommets 4 Nombre d arêtes 6 Distribution des degrés 3 régulier Rayon 1 …   Wikipédia en Français

  • Graphe triangle — Représentation du graphe triangle. Notation C3, K3 Nombre de sommets 3 Nombre d arêtes 3 Distribution des degrés 2 ré …   Wikipédia en Français

  • Graphe de Hoffman — Représentation du graphe de Hoffman. Nombre de sommets 16 Nombre d arêtes 32 Distribution des degrés 4 régulier Rayon 3 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”