On the Brouwer-type Conjecture for Signless Laplacian Eigenvalues of Graphs

Ruisong Yuan; Xiao-Dong Zhang

In the authors' words

Motivated by Brouwer's conjecture, Ashraf, Omidi and Tayfeh-Rezaie proposed the following Brouwer-type conjecture that for every graph $G$ on $n$ vertices with $m$ edges, the sum $S_{k}^{+} (G)$ of its $k$ largest signless Laplacian eigenvalues satisfies $S_{k}^{+} (G) \leq m + (2 k + 1)$ for $k = 1, \dots, n$ . In this paper, we prove that the above conjecture holds. Moreover, the equality holds if and only if $k = 1$ and $G$ is either star $K_{1, a}$ or triangle $K_{3}$ with adding some isolated vertices. For split graphs, properties of block signless Laplacian matrices based on clique and independent set are adapted. While for non-split graphs, some spectral graph substructure are used to control the sum of signless Laplacian eigenvalues.

Main resultThe abstract does not state a limitation.

On the Brouwer-type Conjecture for Signless Laplacian Eigenvalues of Graphs

In the authors' words

More on Combinatorics & discrete math that day

Breaking the Infinite Barrier in the 31​--32​ Conjecture

Proof of the Kahn Saks Conjecture

The Kelly--Trotter conjecture and dimension of poset products

Greedy queens and the golden ratio

2-colouring shift-chains

Breaking the Infinite Barrier in the $\frac{1}{3}$ -- $\frac{2}{3}$ Conjecture