## 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