Algebraic lower-bound conjecture for the complement connectivity pair

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(2xy)n(1x)(1y)(n2xy),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.

Sources & referencesView supporting material

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.