10-cage de Balaban

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
10-cage de Balaban
Image illustrative de l'article 10-cage de Balaban
Représentation de la 10-cage de Balaban

Nombre de sommets 70
Nombre d'arêtes 105
Rayon 6
Diamètre 6
Maille 10
Automorphismes 80
Nombre chromatique 2
Indice chromatique 3
Propriétés Cubique
Cage
Hamiltonien

La 10-cage de Balaban (ou (3,10)-cage de Balaban) est, en théorie des graphes, un graphe régulier possédant 70 sommets et 105 arêtes.

Il porte le nom du mathématicien A. T. Balaban qui en a publié la description en 1972[1].

Propriétés[modifier | modifier le code]

Propriétés générales[modifier | modifier le code]

La 10-cage de Balaban est une (3,10)-cage, c'est-à-dire un graphe minimal en nombres de sommets ayant une maille de 10 et étant régulier de degré 3. Il s'agit de la première cage de ce type à avoir été découverte, mais elle n'est pas unique[2]. La liste complète des (3-10)-cages a été donnée par O'Keefe et Wong en 1980[3]. Il en existe trois distinctes, les deux autres étant le graphe de Harries et le graphe de Harries-Wong[4].

La 10-cage de Balaban est un graphe hamiltonien. Elle possédée 91 440 cycles hamiltoniens distincts.

Le diamètre de la 10-cage de Balaban, l'excentricité maximale de ses sommets, ainsi que son rayon, l'excentricité minimale de ses sommets, sont tous deux égaux à 6. Cela entraine que tous ses sommets appartiennent à son centre. Il s'agit par ailleurs 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. Comme il est régulier de degré 3, ce nombre est optimal. La 10-cage de Balaban est donc un graphe optimalement connecté.

Coloration[modifier | modifier le code]

Le nombre chromatique de la 10-cage de Balaban est 2, c'est-à-dire qu'il est possible de le colorer avec 2 couleurs de tel façon que deux sommets reliés par une arêtes soient toujours de couleurs différentes, et ce nombre est (évidemment) minimal.

L'indice chromatique de la 10-cage de Balaban est 3. Il existe donc une 3-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes, et ce nombre est minimal.

Propriétés algébriques[modifier | modifier le code]

Le groupe d'automorphismes de la 10-cage de Balaban est d'ordre 80.

Le polynôme caractéristique de la matrice d'adjacence de la 10-cage de Balaban est : (x-3) (x-2) (x-1)^8 x^2 (x+1)^8 (x+2) (x+3) (x^2-6)^2 (x^2-5)^4 (x^2-2)^2 (x^4-6 x^2+3)^8.

Représentations[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (en) A. T. Balaban, A trivalent graph of girth ten, J. Combinatorial Theory, Set. B, 12:1-5, 1972
  2. (en) T. Pisanski, M. Boben, D. Marušič et A. Orbanić, The Generalized Balaban Configurations, Preprint 2001 citeseer.ist.psu.edu
  3. (en) M. O'Keefe et P.K. Wong, A smallest graph of girth 10 and valency 3, J. Combin. Theory Ser. B 29 (1980) 91-105.
  4. (en) J. A. Bondy et U. S. R. Murty, Graph Theory with Applications. New York: North Holland, p. 237, 1976.