Cage (théorie des graphes)
# 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.

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 $K_{r+1}$ sur r+1 sommets, et la (r,4)-cage est un graphe biparti complet $K_{r,r}$ sur 2r sommets.

D'autres cages notables incluent les graphiques de Moore :

* (3,5)-cage : Graphe de Petersen, 10 sommets ;
* (3,6)-cage : Graphe de Heawood, 14 sommets ;
* (3,8)-cage : Graphe de Tutte–Coxeter, 30 sommets ;
* (3,10)-cage : 10-cage de Balaban, 70 sommets ;
* (3,11)-cage : 11-cage de Balaban, 112 sommets ;
* (3,12)-cage : 12-cage de Tutte, 126 sommets ;
* (4,5)-cage : Graphe de Robertson, 19 sommets ;
* (7,5)-cage : Graphe de Hoffman-Singleton, 50 sommets ;
* lorsque r − 1 est une puissance première, les cages (r,6) sont les graphes d'incidence des plans projectifs ;
* lorsque r − 1 est une puissance première, les cages (r,8) et (r,12) sont des polygones généralisés (en).

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 :

| gr | 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 | | | | | | |
