Abstract
Denote by qn(G) the smallest eigenvalue of the signless Laplacian matrix of an nvertex graph G. Brandt conjectured in 1997 that for regular triangle-free graphs qn(G) ≤ 4n/25 . We prove a stronger result: If G is a triangle-free graph, then qn(G) ≤ 15n/94 < 4n/25 . Brandt's conjecture is a subproblem of two famous conjectures of Erdos: (1) Sparse-half-conjecture: Every n-vertex triangle-free graph has a subset of vertices of size [n/2] spanning at most n2/50 edges. (2) Every n-vertex triangle-free graph can be made bipartite by removing at most n2/25 edges. In our proof we use linear algebraic methods to upper bound qn(G) by the ratio between the number of induced paths with 3 and 4 vertices. We give an upper bound on this ratio via the method of flag algebras.
Original language | English (US) |
---|---|
Pages (from-to) | 1173-1179 |
Number of pages | 7 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 37 |
Issue number | 2 |
DOIs | |
State | Published - 2023 |
Keywords
- eigenvalues
- graph theory
- triangles
ASJC Scopus subject areas
- General Mathematics