Difference between revisions of "Open problems in degree/girth"
From Combinatorics Wiki
| Line 4: | Line 4: | ||
===Girth 5 graphs=== | ===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)</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)</math> where <math>c<2</math> is a constant? | + | 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<2</math> is a constant? |
Expected difficulty: hard. | Expected difficulty: hard. | ||
Latest revision as of 08:34, 16 July 2023
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.