Difference between revisions of "The Cage Problem"
From Combinatorics Wiki
CW>Gpineda 
m (1 revision imported) 
(No difference)

Latest revision as of 14:39, 3 January 2019
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 stateoftheart 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.
References
 G. Exoo and R. Jajcay (2008), "Dynamic cage survey", The Electronic Journal of Combinatorics, Dynamic survey DS16 PDF version.