Girth constraints for diameter-maximal regular graphs

Let GG be a diameter-maximal regular graph, with diameter DD and girth gg.

Diameter-maximal girth conjecture. If DD is odd, then

g=D+1.g=D+1.

If DD is even, then

g{D,D+1,D+2}.g\in\{D,D+1,D+2\}.

This conjecture is suggested by the authors' search for diameter-maximal graphs, including examples for degree 33 and diameter at most 99 and degree 44 and diameter at most 66. It is stated as an open problem.

Sources & referencesView supporting material

Primary source

Geoffrey Exoo, Theodore Kolokolnikov, Jeanette Janssen and Timothy Salamon, “Attainable bounds for algebraic connectivity and maximally-connected regular graphs”, arXiv:2307.07308 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.