10-cage de Balaban

10-cage de Balaban
10-cage de Balaban
Représentation de la 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
modifier Consultez la documentation du modèle

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

Sommaire

Propriétés

Propriétés générales

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és 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.

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és 3 ce nombre est optimal. La 10-cage de Balaban est donc un graphe optimalement connecté.

Coloriage

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 mais ce nombre est minimal. Il n'existe pas de 1-coloration valide du graphe.

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

Propriétés algébriques

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

Le polynôme caractéristique de la 10-cage de Balaban est : (x − 3)(x − 2)(x − 1)8x2(x + 1)8(x + 2)(x + 3)(x2 − 6)2(x2 − 5)4(x2 − 2)2(x4 − 6x2 + 3)8.

Représentations

  • Représentation du nombre chromatique de la 10-cage de Balaban : 2.

  • Représentation de l'indice chromatique de la 10-cage de Balaban : 3.

  • Représentation alternative du graphe.

Voir aussi

Liens internes

Liens externes

Références

  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.

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • 11-cage de Balaban — Représentation de la 11 cage de Balaban Nombre de sommets 112 Nombre d arêtes 168 Rayon 6 Diamètre 8 …   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

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • South Pacific (musical) — This article is about the 1949 Broadway musical. For the 1958 film, see South Pacific (film). For the 2001 film, see South Pacific (2001 film). South Pacific Original Cast Recording Music Richard Rodgers …   Wikipedia

  • Girth (graph theory) — In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.[1] If the graph does not contain any cycles (i.e. it s an acyclic graph), its girth is defined to be infinity.[2] For example, a 4 cycle (square) has… …   Wikipedia

  • 2003 in film —             List of years in film       (table) … 1993 .  1994 .  1995 .  1996  . 1997  . 1998  . 1999 … 2000 2001 2002 2003 2004 2005 2006 …  …   Wikipedia

  • Bob Roberts — Infobox Film name = Bob Roberts caption = Bob Roberts film poster director = Tim Robbins producer = Forrest Murray writer = Tim Robbins starring = Tim Robbins Giancarlo Esposito Fred Ward Alan Rickman Ray Wise Brian Murray Gore Vidal Rebecca… …   Wikipedia

  • Liste von Kriegsfilmen — Es ist teilweise umstritten, welche Spielfilme als „Kriegsfilme“ gelten können. Wie im Hauptartikel Kriegsfilm dargelegt, gibt es die Auffassung, nur die Thematisierung moderner Kriege rechtfertige das Etikett „Kriegsfilm“. Hiervon abweichend… …   Deutsch Wikipedia

  • 1994 in film —             List of years in film       (table) … 1984 .  1985 .  1986 .  1987  . 1988  . 1989  . 1990 … 1991 1992 1993 1994 1995 1996 1997 …  …   Wikipedia

  • Screen Actors Guild Award for Outstanding Performance by a Cast in a Motion Picture — The Screen Actors Guild Award for Outstanding Performance by a Cast in a Motion Picture is an award given by the Screen Actors Guild to honor the finest acting achievements in film.Winners and nominees1990*1995 Apollo 13 Kevin Bacon, Tom Hanks,… …   Wikipedia

Share the article and excerpts

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