Algebraic lower-bound conjecture for the complement connectivity pair

About 4 years old · traced to

Let GG be a graph on nn vertices, with complement GcG^c, and write

x=λ2(G),y=λ2(Gc).x=\lambda_2(G),\qquad y=\lambda_2(G^c).

Assume that x<1x<1 and y<1y<1.

Algebraic lower-bound conjecture. The pair (x,y)(x,y) satisfies

xy(2−xy)≥n(1−x)(1−y)(n−2−x−y),xy(2-xy)\geq n(1-x)(1-y)(n-2-x-y),

with equality only when GG belongs to one of the three graph families enumerated earlier in the paper. This empirically observed inequality is presented as a strengthening of the symmetric Laplacian Spread Conjecture; its status is unresolved in the source.

References

Primary source

Wayne Barrett, Emily Evans, H. Tracy Hall and Mark Kempton, “New conjectures on algebraic connectivity and the Laplacian spread of graphs”, arXiv:2201.04225 (2022).

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.