Voir la source de Cage de Foster

{{Infobox Graphe
 | nom                = Cage de Foster
 | image              = 
 | légende            = 
 | distribution       = 5-[[Graphe régulier|régulier]]
 | sommets            = 30
 | arêtes             = 75
 | automorphismes     = 30
 | maille             = 5
 | diamètre           = 3
 | rayon              = 3
 | nombre chromatique = 4
 | indice chromatique = 5
 | propriétés         = [[Graphe régulier|Régulier]]<br />[[Cage (graphe)|Cage]]<br />[[Graphe hamiltonien|Hamiltonien]]
}}
La '''cage de Foster''' est, en [[théorie des graphes]], un [[graphe régulier|graphe 5-régulier]] possédant 30 sommets et 75 arêtes.

== Propriétés ==

=== Propriétés générales ===
Le [[Diamètre (théorie des graphes)|diamètre]] de la cage de Foster, l'excentricité maximale de ses sommets, est 3, son [[Rayon (théorie des graphes)|rayon]], l'excentricité minimale de ses sommets, est 3 et sa [[Maille (théorie des graphes)|maille]], la longueur de son plus court [[cycle (graphe)|cycle]], est 5. Il s'agit d'un graphe 5-[[Graphe sommet-connexe|sommet-connexe]] et d'un graphe 5-[[Graphe arête-connexe|arête-connexe]], c'est-à-dire qu'il est [[graphe connexe|connexe]] et que pour le rendre déconnecté il faut le priver au minimum de 5 sommets ou de 5 arêtes.

=== Coloration ===
Le [[nombre chromatique]] de la cage de Foster 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]] de la cage de Foster est 5. Il existe donc une 5-coloration des arêtes du graphe telle 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]]  de la [[matrice d'adjacence]] de la cage de Foster est : <math>(x-5) (x-2)^4 (x+1) (x^2-5)^2 (x^2+2 x-4)^2 (x^4+2 x^3-6 x^2-7 x+11)^4</math>.

== Voir aussi ==

=== Liens internes ===
* [[Théorie des graphes]]
* [[Cage (graphe)]]

=== Liens externes ===
* {{en}} [[Eric W. Weisstein]], [http://mathworld.wolfram.com/FosterCage.html Foster Cage] ([[MathWorld]])

=== Références ===
<references />

{{Portail|Mathématiques}}

[[Catégorie:Graphe remarquable|Foster]]