The normalized Laplacian maximum-connectivity conjecture

About 3 years old · traced to

Let GG be a graph on n≥2n\geq2 vertices, and let L(G)\mathcal{L}(G) be its normalized Laplacian matrix with eigenvalues

0=λ1(G)≤λ2(G)≤⋯≤λn(G).0=\lambda_1(G)\leq\lambda_2(G)\leq\cdots\leq\lambda_n(G).

Normalized Laplacian maximum-connectivity conjecture.

max⁡{λ2(G),λ2(Gc)}≥2n−1.\max\{\lambda_2(G),\lambda_2(G^c)\}\geq \frac{2}{n-1}.

This is a normalized-Laplacian analogue of the Laplacian spread problem and concerns how well-connected a graph or its complement must be. Numerical computations motivate the bound, which remains open.

References

Primary source

J. Nolan Faught, Mark Kempton and Adam Knudson, “A Nordhaus-Gaddum type problem for the normalized Laplacian spectrum and graph Cheeger constant”, arXiv:2304.01979 (2023).

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.