92-graphe de Horton

92-graphe de Horton
92-Graphe de Horton
Nombre de sommets 92
Nombre d'arêtes 138
Distribution des degrés 3-régulier
Rayon 11
Diamètre 12
Maille 6
Nombre chromatique 2
Indice chromatique 3
Propriétés Biparti
Cubique
Régulier
modifier Consultez la documentation du modèle

Le 92-graphe de Horton est, en théorie des graphes, un graphe 3-régulier possédant 92 sommets et 138 arêtes.

Sommaire

Histoire

En 1971, le mathématicien et cryptanalyste William Tutte conjecture qu'il n'existe pas de graphe 3-sommet-connexe qui soit cubique, bipartite et non-hamiltonien[1]. Mais J. D. Horton trouve un contre-exemple à 96 sommets, le graphe de Horton, publié par Bondy & Murty en 1976[2].

Après cela, d'autres contre-exemples sont découverts. En 1982, c'est un graphe à 92 sommets, encore construit par Horton (le 92-graphe de Horton)[3], puis, en 1983, Owens trouve un contre-exemple d'ordre 78[4].

Avec Ellingham, Horton publie deux contre-exemples à la conjecture de Tutte : un graphe d'ordre 78 en 1981 (le 78-graphe de Ellingham-Horton)[5] et un graphe d'ordre 54 en 1983 (le 54-graphe de Ellingham-Horton)[6]. A l'heure actuelle, ce graphe à 54 sommets est le plus petit graphe non-hamiltonien bipartite cubique 3-sommet-connexe connu.

Propriétés

Propriétés générales

Le diamètre du 92-graphe de Horton, l'excentricité maximale de ses sommets, est 12, son rayon, l'excentricité minimale de ses sommets, est 11 et sa maille, la longueur de son plus court cycle, est 6. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

Coloriage

Le nombre chromatique du 92-graphe de Horton est 2. C'est-à-dire qu'il est possible de le colorer avec 2 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal.

L'indice chromatique du 92-graphe de Horton est 3. Il existe donc une 3-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

Voir aussi

Liens internes

Liens externes

Références

  1. ↑ (en) William Tutte, « On the 2-Factors of Bicubic Graphs », dans Discrete Mathematics, Elsevier, vol. 1, no 2, 22 mars 1971, p. 203-208 [lien DOI] .
  2. ↑ (en) J. A. Bondy et U. S. R. Murty, Graph Theory with Applications, New York, North Holland, 1976, 1976e éd. (ISBN 978-0-444-19451-0) [lire en ligne], p. 240 
  3. ↑ (en) J. D. Horton, « On two-factors of bipartite regular graphs », dans Discrete Mathematics, vol. 41, no 1, 1982, p. 35–41 [lien DOI] .
  4. ↑ (en) P. J. Owens, « Bipartite cubic graphs and a shortness exponent », dans Discrete Mathematics, vol. 44, no 3, 1983, p. 327–330 [lien DOI] .
  5. ↑ (en) M. N. Ellingham, Non-Hamiltonian 3-connected cubic partite graphs, Dept. of Math., Univ. Melbourne, 1981 .
  6. ↑ (en) M. N. Ellingham, « Non-Hamiltonian 3-connected cubic bipartite graphs », dans Journal of Combinatorial Theory, Series B, vol. 34, no 3, 1983, p. 350–353 [lien DOI] .

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Graphe de Horton — Représentation du graphe de Horton. Nombre de sommets 96 Nombre d arêtes 144 Distribution des degrés 3 régulier Rayon 10 …   Wikipédia en Français

  • 54-graphe de Ellingham-Horton — Représentation du 54 graphe de Ellingham Horton. Nombre de sommets 54 Nombre d arêtes 81 Distribution des degrés 3 régulier R …   Wikipédia en Français

  • 78-graphe de Ellingham-Horton — Représentation du 78 graphe de Ellingham Horton. Nombre de sommets 78 Nombre d arêtes 117 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Bulle immobilière américaine des années 2000 — La bulle immobilière américaine des années 2000 était une bulle immobilière observée à l échelle nationale aux États Unis sur l ensemble du marché immobilier américain et en particulier en Californie, Floride, Nevada, Oregon, Colorado, Michigan,… …   Wikipédia en Français

  • Bulle immobilière américaine — des années 2000 La bulle immobilière américaine des années 2000 était une bulle immobilière observée à l échelle nationale aux États Unis sur l ensemble du marché immobilier américain et en particulier en Californie, Floride, Nevada, Oregon,… …   Wikipédia en Français

  • Groupe De Higman-Sims — En mathématiques, le groupe de Higman–Sims est un groupe sporadique simple fini d ordre 44 352 000. Il peut être caractérisé comme le sous groupe simple d index 2 dans le groupe des automorphismes du graphe de Higman–Sims. Le graphe de… …   Wikipédia en Français

  • Groupe de Higman-Sims — En mathématiques, le groupe de Higman–Sims est un groupe sporadique simple fini d ordre    29 · 32 · 53 · 7 · 11 = 44 352 000. Il peut être caractérisé comme le sous groupe simple d index 2 dans le groupe des… …   Wikipédia en Français

  • Groupe de higman-sims — En mathématiques, le groupe de Higman–Sims est un groupe sporadique simple fini d ordre 44 352 000. Il peut être caractérisé comme le sous groupe simple d index 2 dans le groupe des automorphismes du graphe de Higman–Sims. Le graphe de… …   Wikipédia en Français

Share the article and excerpts

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