A classical result of Andr\'asfai, Erd\H{o}s, and S\'os 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 $\mu_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 $\mu_2(G)\geq \frac{n}{3}$ is bipartite. Moreover, the constant $\frac{1}{3}$ is asymptotically best possible. 2. For $k\geq 3$, every $n$-vertex graph $G$ of odd girth at least $2k+1$ with $\mu_2(G)>\frac{4n}{6k-1}$ is bipartite. 3. For $k\geq 22$, every $n$-vertex graph $G$ of odd girth at least $2k+1$ with $\mu_2(G)>\frac{3456n}{k^3}$ is bipartite. Moreover, the term $k^{-3}$ is asymptotically best possible.
In 2016, Reiher's clique density theorem determined the minimum number of copies of $K_t$ in a graph with a prescribed edge density. In this paper, we investigate its local version and prove a local clique density theorem in $H$-free graphs as follows. For integers $r$ and $t$ with $2\leq t\leq r-1$, any $r$-chromatic graph $H$, any real numbers $\gamma$ and $\alpha$ with $\frac{t-2}{2(t-1)}\leq\gamma\leq \frac{r-2}{2(r-1)}$ and $0\leq\alpha\leq 1$, we determine the maximum value $\beta:=\beta(r,t,\alpha,\gamma)$ such that for every $n$-vertex $H$-free graph $G$ with at least $\gamma n^2$ edges, every $\lceil\alpha n\rceil$-vertex subset in $G$ contains at least $(\beta-o(1))n^{t}$ copies of $K_t$. In particular, when $H=K_r$, every $\lceil\alpha n\rceil$-vertex subset contains at least $\lfloor\beta n^t\rfloor$ copies of $K_t$, which is an exact bound. For suitable choices of $\alpha$ and $\gamma$, namely, those for which all part ratios in the corresponding extremal construction are rational, this bound is attained for infinitely many values of $n$.
Jiaao Li, Xinyu Li, Yan Wang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
