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).
Known cages.
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 "K""r"+1 on "r"+1 vertices, and the ("r",4)-cage is a complete bipartite graph "K""r","r" on 2"r" vertices.
Notable cages include:
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:
Asymptotics.
For large values of "g", the Moore bound implies that the number "n" of vertices must grow at least singly exponentially as a function of "g". Equivalently, "g" can be at most proportional to the logarithm of "n". More precisely,
It is believed that this bound is tight or close to tight . The best known lower bounds on "g" are also logarithmic, but with a smaller constant factor (implying that "n" grows singly exponentially but at a higher rate than the Moore bound). Specifically, the construction of Ramanujan graphs defined by satisfy the bound
This bound was improved slightly by .
It is unlikely that these graphs are themselves cages, but their existence gives an upper bound to the number of vertices needed in a cage.