Cage (graph theory)

Template:Short description [[Image:Tutte eight cage.svg|thumb|right|The [[Tutte–Coxeter graph|Tutte Template:Nowrap]].]]

In the mathematical field of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.

Formally, an Template:Nowrap is defined to be a graph in which each vertex has exactly Template:Mvar neighbors, and in which the shortest cycle has a length of exactly Template:Mvar. An Template:Nowrap is an Template:Nowrap with the smallest possible number of vertices, among all Template:Nowrap. A Template:Nowrap is often called a Template:Nowrap.

It is known that an Template:Nowrap exists for any combination of Template:Nowrap and Template:Nowrap. It follows that all Template:Nowrap exist.

If a Moore graph exists with degree Template:Mvar and girth Template:Mvar, it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth Template:Mvar must have at least

$1+r\sum _{i=0}^{(g-3)/2}(r-1{)}^i$

vertices, and any cage with even girth Template:Mvar must have at least

$2\sum _{i=0}^{(g-2)/2}(r-1{)}^i$

vertices. Any Template:Nowrap 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 Template:Mvar and Template:Mvar. For instance there are three non-isomorphic Template:Nowrap, each with 70 vertices: the Template:Nowrap, the Harries graph and the Harries–Wong graph. But there is only one Template:Nowrap: the Template:Nowrap (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 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.

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:

Template:Diagonal split header	3	4	5	6	7	8	9	10	11	12
3	4	6	10	14	24	30	58	70	112	126
4	5	8	19	26	67	80				728
5	6	10	30	42		170				2730
6	7	12	40	62		312				7812
7	8	14	50	90

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,

$g\le 2{\log }_{r-1}n+O(1).$

It is believed that this bound is tight or close to tight Template:Harv. 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 Template:Harvtxt satisfy the bound

$g\ge \frac{4}{3}{\log }_{r-1}n+O(1).$

This bound was improved slightly by Template:Harvtxt.

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.

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.

External links

• Brouwer, Andries E. Cages
• Royle, Gordon. Cubic Cages and Higher valency cages
• Template:Mathworld