Graphe de Wells

Graphe de Wells
Graphe de Wells
Nombre de sommets 32
Nombre d'arêtes 80
Distribution des degrés 5-régulier
Rayon 4
Diamètre 4
Maille 5
Nombre chromatique 4
Indice chromatique 5
Propriétés Régulier
Hamiltonien
Cayley
Arête-transitif
Sommet-transitif
Distance-transitif

Le graphe de Wells est, en théorie des graphes, un graphe 5-régulier possédant 32 sommets et 80 arêtes.

Sommaire

Propriétés

Propriétés générales

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

Coloriage

Le nombre chromatique du graphe de Wells est 4. C'est-à-dire qu'il est possible de le colorer avec 4 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 3-coloration valide du graphe.

L'indice chromatique du graphe de Wells est 5. Il existe donc une 5-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.

Propriétés algébriques

Le polynôme caractéristique du graphe de Wells est : (x − 5)(x − 1)10(x + 3)5(x2 − 5)8. Il existe trois autres graphes ayant le même spectre, l'ensemble des valeurs propres de sa matrice d'adjacence[1].

Voir aussi

Liens internes

Liens externes

Références

  1. van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.

Wikimedia Foundation. 2010.

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

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

Regardez d'autres dictionnaires:

  • 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

  • Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

  • Eulérien — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

  • Leonard Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

  • Leonhard Euler — « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler Portrait par Johann Georg Brucker Naissance …   Wikipédia en Français

  • Leonhard Paul Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

  • Léonard Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

  • Scale-invariant feature transform — Exemple de résultat de la comparaison de deux images par la méthode SIFT (Fantasia ou Jeu de la poudre, devant la porte d’entrée de la ville de Méquinez, par Eug …   Wikipédia en Français

  • Cyprus — This article is about the island sovereign state. For other uses, see Cyprus (disambiguation). Republic of Cyprus Κυπριακή Δημοκρατία (Greek) Kypriakí Dimokratía Kıbrıs Cumhuriyeti (Turkish) …   Wikipedia

  • Minoan civilization — Map of Minoan Crete History of Greece …   Wikipedia

Share the article and excerpts

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