The Cage Problem

The Cage Problem

This problem, also known as the degree/girth problem, is closely related to the degree/diameter problem.

Degree/girth problem: Given natural numbers d≥2 and g≥3, find the smallest possible number n(d,g) of vertices in a regular graph of degree d and girth g.

A regular graph of degree d, girth g and minimum possible order is called a (d,g)-cage. Tutte was the first to study (d,g)-cage. However, researchers became really interested in this class of graphs when Erdos and Sachs proved that a (d,g)-cage exists for all d≥2 and g≥3, implying that the function n(d,g) is defined for any d≥2 and g≥3. At present only a few (d,g)-cages are known. The state-of-the-art in the study of cages can be found in the recently published survey by Exoo and Jajcay.

It turns out that lower bounds for (d,g)-cage depends on the parity of g; that is why the degree/girth problem is often divided into the degree/girth problem for odd girth and the degree/girth problem for even girth.

Degree/girth problem for odd girth: Given natural numbers d≥2 and odd g≥3, find the smallest possible number n(d,g) of vertices in a regular graph of degree d and girth g.

Degree/girth problem for odd girth: Given natural numbers d≥2 and even g≥3, find the smallest possible number n(d,g) of vertices in a regular graph of degree d and girth g.

The Moore bound represents not only an upper bound on the number N(d,k) of vertices of a graph of maximum degree d and diameter k, but it is also a lower bound on the number n^o(d,g) of vertices of a regular graph of degree d and girth 2k+1 . A (d,g)-cage of order M(d,k) is therefore a Moore graph if g=2k+1.

The Moore bipartite bound represents not only an upper bound on the number of vertices of a bipartite graph of maximum degree d and diameter k, but it is also a lower bound on the number n^e(d,g) of vertices of a regular graph of degree d and girth g=2k.

Then a preamble about tables....

Now a link to a table for trivalent graphs.

• Tables and Results

References

• G. Exoo and R. Jajcay (2008), "Dynamic cage survey", The Electronic Journal of Combinatorics, Dynamic survey DS16 PDF version.