Covering-number bound for Laplacian eigenvalue sums

From papers

Let G=(V,E)G=(V,E) be a graph, let τ(G)\tau(G) denote its covering number, and let L(G)L(G) be the Laplacian matrix of GG. For 1iV1\leq i\leq |V|, write λi(L(G))\lambda_i(L(G)) for the ii-th largest Laplacian eigenvalue. Covering-number conjecture. For all τ(G)kV\tau(G)\leq k\leq |V|,

i=1kλi(L(G))E+kτ(G)(τ(G)2).\sum_{i=1}^k \lambda_i(L(G)) \leq |E|+k\cdot\tau(G)-\binom{\tau(G)}{2}.

This conjecture proposes a sharper relation between Laplacian eigenvalue sums and the vertex covering number. The paper proves related bounds involving covering and matching numbers, but the displayed inequality is proposed as an open strengthening.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Alan Lew, “Partition density, star arboricity, and sums of Laplacian eigenvalues of graphs”, arXiv:2410.04563 (2024).

Solutions 0

No solutions have been posted yet.