Cage (théorie des graphes)

En théorie des graphes, une cage est un graphe régulier minimal pour une maille donnée. Plus précisément, une (r,g)-cage est un graphe régulier minimal de degré r et de maille g.

Pour les articles homonymes, voir Cage.

Quand le terme de g-cage est employé, il s'agit en fait d'une cage cubique, c'est-à-dire d'une (3,g)-cage.

Cages connues

Un graphe degré-un n'a pas de cycle, et un graphe degré-deux connexe a une circonférence égale à son nombre de sommets, donc les cages ne présentent un intérêt que pour r ≥ 3. La (r,3)-cage est un graphe complet Kr+1 sur r+1 sommets, et la (r,4)-cage est un graphe biparti complet Kr,r sur 2r sommets.

D'autres cages notables incluent les graphiques de Moore :

Le nombre de sommets dans les cages connues (r,g), pour les valeurs de r > 2 et g > 2, autres que les plans projectifs et les polygones généralisés, sont :

g
r
3456789101112
3 46101424305870112126
4 5819266780728
5 61030421702730
6 71240623127812
7 8145090

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cage (graph theory) » (voir la liste des auteurs).
    • Portail des mathématiques
    Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.