The equality characterization for the normalized Laplacian maximum bound

Let GG be a graph on n5n\geq5 vertices, with normalized Laplacian 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-bound conjecture.

max{λ2(G),λ2(Gc)}2n1\max\{\lambda_2(G),\lambda_2(G^c)\}\geq\frac{2}{n-1}

with equality if and only if nn is odd and GG is the join of an isolated vertex with two complete graphs, each of order n12\frac{n-1}{2}. This conjecture refines the proposed lower bound by specifying all equality cases. The paper presents it as an open problem supported by computations and identifies the displayed graph family for odd orders.

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.