The normalized Laplacian maximum-connectivity conjecture

Let GG be a graph on n2n\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)}2n1.\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.

Sources & referencesView supporting material

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.