| Autor: |
BALOGH, JÓZSEF, CLEMEN, FELIX CHRISTIAN, LIDICKÝ, BERNARD, NORIN, SERGEY, VOLEC, JAN |
| Předmět: |
|
| Zdroj: |
SIAM Journal on Discrete Mathematics; 2023, Vol. 37 Issue 2, p1173-1179, 7p |
| Abstrakt: |
Denote by qn (G) the smallest eigenvalue of the signless Laplacian matrix of an n-vertex 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 Erdőos: (1) Sparse-half-conjecture: Every n-vertex triangle-free graph has a subset of vertices of size [n\2] spanning at most n²/50 edges. (2) Every n-vertex triangle-free graph can be made bipartite by removing at most n²/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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
