Grahame: 1 revision imported

2019-01-03T14:39:32Z

1 revision imported

CW>Gpineda at 04:00, 30 January 2009

2009-01-30T04:00:04Z

New page

==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<sup>o</sup>(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<sup>e</sup>(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 [http://www.combinatorics.org/Surveys/ds16.pdf PDF version].

[[Category:The Cage Problem]]

← Older revision	Revision as of 14:39, 3 January 2019
(No difference)

The Cage Problem - Revision history

Grahame: 1 revision imported

CW>Gpineda at 04:00, 30 January 2009