Covering-number bound for Laplacian eigenvalue sums

About 2 years old · traced to

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 1≤i≤∣V∣1\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)≤k≤∣V∣\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.

References

Primary source

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

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.