Open problems in degree/girth

From Combinatorics Wiki

Revision as of 08:34, 16 July 2023 by Grahame (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

This page lists a number of open problems in the degree/girth (cage) problem.

For the background and history of the problem, see G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin. DS16 (2012).

Girth 5 graphs

The current best known constructions for degree [math]d[/math] and girth 5 in the undirected cage problem have order [math]2d^2+o(d^2)[/math]. (See the survey for details.) This is asymptotically the same as the best graphs of girth 6. Is it possible to construct an infinite family of graphs of degree [math]d[/math] and girth 5 with order [math]cd^2+o(d^2)[/math] where [math]c\lt 2[/math] is a constant?

Expected difficulty: hard.