The improved diameter and order bounds for cubic graphs

Let GG be a cubic graph, and let DD be its diameter. The cubic-graph algebraic-connectivity bound conjecture. Its algebraic connectivity satisfies

λ2(G)323/2cos(πD).\lambda_{2}(G)\leq 3-2^{3/2}\cos\left(\frac{\pi}{D}\right).

Moreover, if GG has order n=2K+12n=2^{K+1}-2, then

λ2(G)323/2cos(πK).\lambda_{2}(G)\leq 3-2^{3/2}\cos\left(\frac{\pi}{K}\right).

These conjectured bounds are numerical improvements over the cited Nilli bound and are posed as open conjectures in the source.

Sources & referencesView supporting material

Primary source

Theodore Kolokolnikov, “Maximizing algebraic connectivity for certain families of graphs”, arXiv:1412.6147 (2014).

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.