On the structure of graphs with given odd girth and large algebraic connectivity
A classical result of Andrásfai, Erdős, and Sós states that every $n$-vertex graph with odd girth at least $2k+1$ and minimum degree larger than $\frac{2n}{2k+1}$ is bipartite. Rather than imposing a minimum-degree condition, in this paper we investigate conditions on algebraic connectivity that force graphs of given odd girth to have a simple structure. The algebraic connectivity of a graph $G$, denoted by $μ_2(G)$, is the second smallest eigenvalue of its Laplacian matrix. Our main results are as follows. 1. Every $n$-vertex triangle-free graph $G$ with $μ_2(G)\geq \frac{n}{3}$ is…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.30799
curl -X POST /api/v1/records/arxiv/2608.30799/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.30799/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'