Weighted Laplacian Spread Conjecture

About 4 years old · traced to

Let GG be a weighted graph on nn vertices in which every edge weight lies in [0,1][0,1], and let GcG^c be its weighted complement, obtained by replacing each edge weight wijw_{ij} by 1−wij1-w_{ij}. The algebraic connectivity of a weighted graph is denoted by λ2\lambda_2.

Weighted Laplacian Spread Conjecture. One has

λ2(G)+λ2(Gc)≥1.\lambda_2(G)+\lambda_2(G^c)\geq 1.

This is the natural extension of the symmetric formulation of the Laplacian Spread Conjecture from simple graphs to weighted graphs; the paper reports supporting investigations but no resolution.

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.