OpenAlex ·
The least signless Laplacian eigenvalue of $\{C_3,C_5\}$-free graphs
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.00875
- Original
- Read it at the publisher
- Topics
Abstract
Brandt [Discrete Math. 183 (1998) 17--25] conjectured that the least signless Laplacian eigenvalue of every regular triangle-free graph of order $n$ is at most $4n/25$. Using flag algebras, Balogh, Clemen, Lidický, Norin and Volec [SIAM J. Discrete Math. 37 (2023) 1173--1179] established the stronger bound $15n/94$ for all triangle-free graphs. We investigate the effect of additionally excluding pentagons and prove that every $\{C_3,C_5\}$-free graph $G$ of order $n$ satisfies $\qmin(G)<0.0569n$, without any regularity assumption. The proof combines seven-vertex flag inequalities with local Rayleigh constraints that retain the least eigenvalue throughout the counting argument. An exact integer certificate establishes the required inequality.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Coloring 3-colorable graphs with $O(n^{4/23})$ colors via a Gaussian-cover recursion
Grid Theory and Polynomiality in Dynamic Lot-Sizing
Stable and Online Algorithms for Random Matrix Discrepancy
The Coverage Depth Problem in Distributed DNA Data Storage
Resolving Erdős-Ulam Monochromatic Union-Closed Family Conjectures
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.