The improved diameter and order bounds for cubic graphs

About 12 years old · traced to

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)≤3−23/2cos⁡(πD).\lambda_{2}(G)\leq 3-2^{3/2}\cos\left(\frac{\pi}{D}\right).

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

λ2(G)≤3−23/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.

References

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.