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 a length of exactly g. An (r, g)-cage is an (r, g)-graph with the smallest 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.

Any (r, g)-graph with exactly this many vertices is by definition a Moore graph and therefore automatically a cage.

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: 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 (Bollobás & Szemerédi 2002).

Specifically, the construction of Ramanujan graphs defined by Lubotzky, Phillips & Sarnak (1988) satisfy the bound This bound was improved slightly by Lazebnik, Ustimenko & Woldar (1995).