Difference between revisions of "Open problems in degree/girth"
From Combinatorics Wiki
(Created page with "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, E...") |
|||
| Line 1: | Line 1: | ||
This page lists a number of open problems in the degree/girth (cage) problem. | 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). | + | 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=== | ===Girth 5 graphs=== | ||
| − | The current best known constructions for degree <math>d</math> and girth 5 | + | 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? |
| + | |||
| + | Expected difficulty: hard. | ||
Revision as of 08:17, 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)[/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\lt 2[/math] is a constant?
Expected difficulty: hard.