Cage (graph theory)

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. An (r, g)-cage is an (r, g)-graph with the smallest possible number of vertices, among all (r, g)-graphs. A (3, g)-cage is often called a g-cage. It is known that an (r, g)-graph exists for any combination of r ≥ 2 and g ≥ 3. It follows that all (r, g)-cages exist. 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 1-regular graph has no cycle, and a connected 2-regular 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. Notable cages include: (3,5)-cage: the Petersen graph, 10 vertices (3,6)-cage: the Heawood graph, 14 vertices (3,7)-cage: the McGee graph, 24 vertices (3,8)-cage: the Tutte–Coxeter graph, 30 vertices (3,10)-cage: the Balaban 10-cage, 70 vertices (3,11)-cage: the Balaban 11-cage, 112 vertices (4,5)-cage: the Robertson graph, 19 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.