Cage (graphe)

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour les articles homonymes, voir Cage.

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.

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[modifier | modifier le code]

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 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
3 4 5 6 7 8 9 10 11 12
3 4 6 10 14 24 30 58 70 112 126
4 5 8 19 26 67 80 728
5 6 10 30 42 170 2730
6 7 12 40 62 312 7812
7 8 14 50 90

Notes et références[modifier | modifier le code]

(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).