11-cage de Balaban

11-cage de Balaban
11-cage de Balaban
Représentation de la 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
Maille 11
Automorphismes 64
Nombre chromatique 3
Indice chromatique 3
Propriétés Cubique
Cage
Hamiltonien
modifier Consultez la documentation du modèle

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

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

Sommaire

Propriétés

Propriétés générales

La 11-cage de Balaban est une (3,11)-cage, c'est-à-dire un graphe minimal en nombres de sommets ayant une maille de 11 et étant régulier de degrés 3. C'est en fait l'unique (3-11)-cage. Cette unicité a été prouvée par McKay et Myrvold en 2003[2].

Le diamètre de la 11-cage de Balaban, l'excentricité maximale de ses sommets, est 8, et son rayon, l'excentricité minimale de ses sommets, 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 de la 11-cage de Balaban est 3. C'est-à-dire qu'il est possible de le colorer avec 3 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 2-coloration valide du graphe.

L'indice chromatique de la 11-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 11-cage de Balaban est un groupe d'ordre 64[3]..

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

Représentations

  • Représentation du nombre chromatique de la 11-cage de Balaban : 3.

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

  • Représentation alternative du graphe[4].

Voir aussi

Liens internes

Liens externes

Références

  1. ↑ (en) A. T. Balaban, Trivalent Graphs of Girth Nine and Eleven and Relationships Among the Cages, Rev. Roumaine Math., 18, 1033-1043, 1973
  2. ↑ (en) Cage Graph, MathWorld
  3. ↑ (en) Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008)
  4. ↑ (en) P. Eades, J. Marks, P. Mutzel, S. North, Graph-Drawing Contest Report, Mitsubishi Electric Research Laboratories, TR98-16, 1998

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • 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 …   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”