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 |
|
|
|
|
|
|
Notes et références
