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 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 :
- (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 :
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 |