Graphe de Foster

Graphe de Foster
Graphe de Foster
Représentation du graphe de Foster
Représentation du graphe de Foster
Nombre de sommets 90
Nombre d'arêtes 135
Distribution des degrés 3-régulier
Rayon 8
Diamètre 8
Maille 10
Automorphismes 4 320
Nombre chromatique 2
Indice chromatique 3
Propriétés Régulier
Cubique
Hamiltonien
Arête-transitif
Distance-transitif
Sommet-transitif
Cayley
Symétrique
modifier Consultez la documentation du modèle

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

Sommaire

Propriétés

Propriétés générales

Le diamètre du graphe de Foster, l'excentricité maximale de ses sommets, est 8, son rayon, l'excentricité minimale de ses sommets, est 8 et sa maille, la longueur de son plus court cycle, est 10. 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 graphe de Foster 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 graphe de Foster 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.

Propriétés algébriques

Le groupe d'automorphismes du graphe de Foster est un groupe d'ordre 4 320.

Le polynôme caractéristique du graphe de Foster est : (x − 3)(x − 2)9(x − 1)18x10(x + 1)18(x + 2)9(x + 3)(x2 − 6)12.

Voir aussi

Liens internes

Liens externes

Références



Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Graphe distance-régulier — En théorie des graphes, un graphe est distance régulier si pour tous sommets , le nombre de sommets voisins de u à distance i et le nombre de sommets voisins de v à distance j ne dépendent que de i,j et de la distance d(u,v) entre u et v.… …   Wikipédia en Français

  • Graphe de Nauru — Représentation du graphe de Nauru. Notation F24A Nombre de sommets 24 Nombre d arêtes 36 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe hexaédrique — Représentation du graphe hexaédrique. Nombre de sommets 8 Nombre d arêtes 12 Distribution des degrés 3 régulier Rayon 3 …   Wikipédia en Français

  • Graphe tétraédrique — Représentation du graphe tétraédrique. Nombre de sommets 4 Nombre d arêtes 6 Distribution des degrés 3 régulier Rayon 1 …   Wikipédia en Français

  • Graphe de Coxeter — Représentation du graphe de Coxeter. Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Rayon 4 …   Wikipédia en Français

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

  • Graphe de Pappus — Le graphe de Pappus Nombre de sommets 18 Nombre d arêtes 27 Distribution des degrés 3 régulier Rayon 4 Diamètre …   Wikipédia en Français

  • Graphe de Biggs-Smith — Représentation du graphe de Biggs Smith Nombre de sommets 102 Nombre d arêtes 153 Rayon 7 Diamètre 7 …   Wikipédia en Français

  • Graphe De Coxeter — Le graphe de Coxeter Nombre de sommets 28 Nombre d arêtes 42 Distribution des degrés 3 régulier Diamètre 4 Propriétés Hypohamilton …   Wikipédia en Français

Share the article and excerpts

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