Girth constraints for diameter-maximal regular graphs

About 3 years old · traced to

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.

References

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.