In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an (r,g)-graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. It is known that an (r,g)-graph exists for any combination of r ≥ 2 and g ≥ 3. An (r,g)-cage is an (r,g)-graph with the fewest possible number of vertices, among all (r,g)-graphs. If a Moore graph exists with degree r and girth g, it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth g must have at least
- <math>1+r\sum_{i=0}^{(g-3)/2}(r-1)^i</math>
vertices, and any cage with even girth g must have at least
- <math>2\sum_{i=0}^{(g-2)/2}(r-1)^i</math>
vertices. Any (r,g)-graph with exactly this many vertices is by definition a Moore graph and therefore automatically a cage. There may exist multiple cages for a given combination of r and g. For instance there are three nonisomorphic (3,10)-cages, each with 70 vertices.
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
- (7,5)-cage: The Hoffman–Singleton graph, 50 vertices
The known (3,g) cages, starting from g = 4, have numbers of vertices
The known (r,g) cages, for higher values of r, starting in each case from g = 4, are (sequence A054760 in OEIS)
- r = 4: 5, 8, 19, 26, 67, 80, 275, 384
- r = 5: 6, 10, 30, 42, 152, 170
- r = 6: 7, 12, 40, 62, 294, 312
- r = 7: 8, 14, 50, 90
| g: | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| r = 3: | 4 | 6 | 10 | 14 | 24 | 30 | 58 | 70 |
|---|---|---|---|---|---|---|---|---|
| r = 4: | 5 | 8 | 19 | 26 | 67 | 80 | 275 | 384 |
| r = 5: | 6 | 10 | 30 | 42 | 152 | 170 | ||
| r = 6: | 7 | 12 | 40 | 62 | 294 | 312 | ||
| r = 7: | 8 | 14 | 50 | 90 |
In addition, several (r,12)-cages are known. Starting at r = 3, the number of vertices in these cages are
- 126, 728, 2730, 7812
References
- Biggs, Norman (1993). Algebraic Graph Theory, 2nd ed., Cambridge Mathematical Library, 180–190. ISBN 0-521-45897-8.
- Hartsfield, Nora; Ringel, Gerhard (1990). Pearls in Graph Theory: A Comprehensive Introduction. Academic Press, 77–81. ISBN 0-12-328552-6.
- D. A. Holton and J. Sheehan (1993). The Petersen Graph. Cambridge University Press, 183–213. ISBN 0-521-43594-3.
- Tutte, W. T. (1947). "A family of cubical graphs.". Proc. Cambridge Philos. Soc. 43: 459–474.
External links
- Brouwer, Andries E. Cages
- Royle, Gordon. Cubic Cages and Higher valency cages
- Eric W. Weisstein, Cage Graph at MathWorld.
