Improved matching-number bound for Laplacian eigenvalue sums

From papers

Let G=(V,E)G=(V,E) be a graph with nn non-isolated vertices, and let ν(G)\nu(G) denote the maximum size of a matching in GG. Let L(G)L(G) be the Laplacian matrix of GG, with eigenvalues λ1(L(G))λn(L(G))\lambda_1(L(G))\geq\cdots\geq\lambda_n(L(G)). Improved matching-number conjecture. If 1kn21\leq k\leq n-2, then

i=1kλi(L(G))E+kν(G).\sum_{i=1}^k \lambda_i(L(G))\leq |E|+k\cdot\nu(G).

The paper presents this as a stronger bound suggested by equality cases for a proved matching-number estimate. The restriction to kn2k\leq n-2 is necessary for the complete graph of odd order, although the paper notes that it is not a significant restriction because the eigenvalue sum equals 2E2|E| for kn1k\geq n-1.

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.