A sharp bound for the least signless Laplacian eigenvalue of triangle-free graphs
Abstract
We prove that every finite simple triangle-free graph G on n≥1 vertices satisfies qmin(G)≤7n/50, where qmin(G) is the least eigenvalue of its signless Laplacian matrix QG=DG+AG, with DG the diagonal matrix of vertex degrees and AG the adjacency matrix. The constant is sharp, since the Higman--Sims graph and its balanced blow-ups attain equality, as shown by de Lima, Nikiforov and Oliveira (2016). This proves the bound conjectured by Balogh, Clemen, Lidický, Norin and Volec (2023). The proof uses five test column vectors associated with an ordered edge to obtain a matrix Rayleigh inequality. Our use of local Rayleigh inequalities together with flag-algebra semidefinite programming is inspired by Zhou (2026). We use semidefinite programming and rational approximation to find the required positive semidefinite matrices, and complete the proof by exact correction and verification.
Related
- The least signless Laplacian eigenvalue of {C3,C5}-free graphs
- A proof of the maximum Laplacian energy conjecture for connected graphs via a sharp eigenvalue-sum bound
- The Distance Laplacian and Distance Signless Laplacian Spectra of 𝒞-Graphs
- On the Brouwer-type Conjecture for Signless Laplacian Eigenvalues of Graphs
- Characterization of graphs attaining the maximum signless Laplacian spectral radius under forbidden cycles and theta graphs
BibTeX
@misc{cai2026sharp,
title = {{A sharp bound for the least signless Laplacian eigenvalue of triangle-free graphs}},
author = {Dongxiu Cai and Zhengbo Chen and Xiao-Dong Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14503},
eprint = {2610.14503},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14503},
}
RIS
TY - UNPB
TI - A sharp bound for the least signless Laplacian eigenvalue of triangle-free graphs
AU - Dongxiu Cai
AU - Zhengbo Chen
AU - Xiao-Dong Zhang
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14503
UR - https://arxiv.org/abs/2610.14503
AB - We prove that every finite simple triangle-free graph G on n≥1 vertices satisfies q_min(G)≤7n/50, where q_min(G) is the least eigenvalue of its signless Laplacian matrix Q_G=D_G+A_G, with D_G the diagonal matrix of vertex degrees and A_G the adjacency matrix. The constant is sharp, since the Higman--Sims graph and its balanced blow-ups attain equality, as shown by de Lima, Nikiforov and Oliveira (2016). This proves the bound conjectured by Balogh, Clemen, Lidický, Norin and Volec (2023). The proof uses five test column vectors associated with an ordered edge to obtain a matrix Rayleigh inequality. Our use of local Rayleigh inequalities together with flag-algebra semidefinite programming is inspired by Zhou (2026). We use semidefinite programming and rational approximation to find the required positive semidefinite matrices, and complete the proof by exact correction and verification.
ER -