A maximum matching based refinement of Brouwers conjecture
Abstract
Let G be a simple graph on n vertices and e(G) edges. Let μ1≥ ⋯ ≥ μn−1≥ μn=0 be the Laplacian eigenvalues of G. For k=1, …, n, let Sk(G)=∑i=1kμi. Brouwers conjecture asserts that for any k∈{1,…, n}, Sk(G)≤ e(G)+binomk+12. In [Bounding the sum of the largest Laplacian eigenvalues of graphs, {\em Discrete Appl. Math.}, 170:95--103, (2014)], Rocha and Trevisan showed that the conjecture holds true for 1 ≤ k ≤ ⌊ g/5 ⌋, where g denotes the girth of G. This bound on k was later improved by Chen in [Improved results on Brouwers conjecture for sum of the Laplacian eigenvalues of a graph, {\em Linear Algebra Appl.}, 557:327--338, (2018)], who established that the conjecture holds for 1 ≤ k ≤ ⌊ g/4 ⌋. In this article, we further strengthen these results by proving that the Brouwers conjecture holds for 1≤ k≤⌊ m(G)/2⌋, where m(G) denotes the matching number of G. Since m(G)≥ ⌊ g/2⌋, the case constitutes a genuine improvement over the aforementioned results. As an application, we show that if G is a graph of order n and with a perfect matching, then the Brouwers conjecture holds for 1≤ k≤ ⌊ n/4⌋. Finally, we provide a new perspective on verifying Brouwers conjecture by proving that G satisfies the Brouwers conjecture if and only if for a fixed positive integer h, 𝒮h(G̅)≤ e(G̅)+binomh+12 holds whenever 𝒮h(G)≤ e(G)+binomh+12, where G̅ denotes the complement of G.
Related
- The maximum number of edges in minimal matching covered graphs
- Central Limit Theorem of Maximum Weight Matching on Random Graphs with Prescribed Degrees
- The maximum size of simple solid matching covered graphs
- Connecting Score Matching, Maximum Likelihood, and Expectation-Maximization in Mixed Linear Regression
- Counterexamples to Sato's Weak F-Equivalence Conjecture and a Gorenstein Refinement
BibTeX
@misc{shamsher2026maximum,
title = {{A maximum matching based refinement of Brouwers conjecture}},
author = {Tahir Shamsher},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12673},
eprint = {2609.12673},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12673},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A maximum matching based refinement of Brouwers conjecture
AU - Tahir Shamsher
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12673
UR - https://arxiv.org/abs/2609.12673
AB - Let G be a simple graph on n vertices and e(G) edges. Let μ_1≥ ⋯ ≥ μ_n−1≥ μ_n=0 be the Laplacian eigenvalues of G. For k=1, …, n, let S_k(G)=∑_i=1^kμ_i. Brouwers conjecture asserts that for any k∈{1,…, n}, S_k(G)≤ e(G)+binomk+12. In [Bounding the sum of the largest Laplacian eigenvalues of graphs, {\em Discrete Appl. Math.}, 170:95--103, (2014)], Rocha and Trevisan showed that the conjecture holds true for 1 ≤ k ≤ ⌊ g/5 ⌋, where g denotes the girth of G. This bound on k was later improved by Chen in [Improved results on Brouwers conjecture for sum of the Laplacian eigenvalues of a graph, {\em Linear Algebra Appl.}, 557:327--338, (2018)], who established that the conjecture holds for 1 ≤ k ≤ ⌊ g/4 ⌋. In this article, we further strengthen these results by proving that the Brouwers conjecture holds for 1≤ k≤⌊ m(G)/2⌋, where m(G) denotes the matching number of G. Since m(G)≥ ⌊ g/2⌋, the case constitutes a genuine improvement over the aforementioned results. As an application, we show that if G is a graph of order n and with a perfect matching, then the Brouwers conjecture holds for 1≤ k≤ ⌊ n/4⌋. Finally, we provide a new perspective on verifying Brouwers conjecture by proving that G satisfies the Brouwers conjecture if and only if for a fixed positive integer h, 𝒮_h(G̅)≤ e(G̅)+binomh+12 holds whenever 𝒮_h(G)≤ e(G)+binomh+12, where G̅ denotes the complement of G.
ER -