Even-diameter order conjecture for chordal ring graphs

Let CR(N,c)CR(N,c) be a chordal ring graph with diameter kk, and let N(k)N(k) denote the maximum number of vertices among chordal ring graphs of diameter kk. For even k>2k>2, the conjecture concerns the largest possible order of such a graph. Even-diameter chordal-ring conjecture. The maximum number NN of vertices of a chordal ring graph with an even diameter k>2k>2 is

N=3k22k.N=\frac{3k^2}{2}-k.

The bound N(k)=3k22N(k)=\frac{3k^2}{2} is known for even diameter, but cannot be attained when k>2k>2; the conjecture proposes the exact next-best value.

Sources & referencesView supporting material

Primary source

M. A. Reyes, C. Dalfó and M. A. Fiol, “Structural and Spectral Properties of Chordal Ring, Multi-ring and Mixed Graphs”, arXiv:2409.00520 (2024).

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.