Cage (graph theory)
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
vertices, and any cage with even girth g must have at least
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 : the Balaban 10-cage, the Harries graph and the Harries-Wong graph. But there is only one (3,11)-cage : the Balaban 11-cage (with 112 vertices).
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:
|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|
- Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge Mathematical Library. pp. 180–190. ISBN 0-521-45897-8.
- Exoo, G; Jajcay, R (2008). "Dynamic Cage Survey". Electronic Journal of Combinatorics. Dynamic Survey DS16.
- Erdõs, Paul; Rényi, Alfréd; Sós, Vera T. (1966). "On a problem of graph theory". Studia Sci. Math. Hungar. 1: 215–235.
- Hartsfield, Nora; Ringel, Gerhard (1990). Pearls in Graph Theory: A Comprehensive Introduction. Academic Press. pp. 77–81. ISBN 0-12-328552-6.
- D. A. Holton and J. Sheehan (1993). The Petersen Graph. Cambridge University Press. pp. 183–213. ISBN 0-521-43594-3.
- Tutte, W. T. (1947). "A family of cubical graphs". Proc. Cambridge Philos. Soc. 43 (4): 459–474. doi:10.1017/S0305004100023720.