Known Cages
A degree-one graph has no cycle, and a connected degree-two graph has girth equal to its number of vertices, so cages are only of interest for r ≥ 3. The (r,3)-cage is a complete graph Kr+1 on r+1 vertices, and the (r,4)-cage is a complete bipartite graph Kr,r on 2r vertices.
Other notable cages include the Moore graphs:
- (3,5)-cage: the Petersen graph, 10 vertices
- (3,6)-cage: the Heawood graph, 14 vertices
- (3,8)-cage: the Tutte–Coxeter graph, 30 vertices
- (3,10)-cage: the Balaban 10-cage, 70 vertices
- (7,5)-cage: The Hoffman–Singleton graph, 50 vertices.
- When r-1 is a prime power, the (r,6) cages are the incidence graphs of projective planes.
- When r-1 is a prime power, the (r,8) and (r,12) cages are generalized polygons.
The numbers of vertices in the known (r,g) cages, for values of r > 2 and g > 2, other than projective planes and generalized polygons, are:
| g: | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| r = 3: | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 | 112 | 126 |
|---|---|---|---|---|---|---|---|---|---|---|
| r = 4: | 5 | 8 | 19 | 26 | 67 | 80 | 728 | |||
| r = 5: | 6 | 10 | 30 | 42 | 170 | 2730 | ||||
| r = 6: | 7 | 12 | 40 | 62 | 312 | 7812 | ||||
| r = 7: | 8 | 14 | 50 | 90 |
Read more about this topic: Cage (graph Theory)