Extremal graph without cycle length $k$ or longer.

291 Views Asked by At

When $k\geq 3$, denote $\mathcal{C}_{k}=\left\{C_{n}\mid n\geq k\right\}$ the family of cycles of graph.

I am trying to find ${\rm{ex}}\left(n;\mathcal{C}_{k}\right)$ and ${\rm{EX}}\left(n;\mathcal{C}_{k}\right)$. The following is my attempt:

I have known that the extremal graph forbidden the path $P_{k+1}$ ($k+1$ vertices.) : $${\rm{EX}}\left(n;P_{k+1}\right)=\left\{G_{n,k},G_{n,k,\ell}\right\}.$$

Write $n=kq+r$ with $0\leq r<k$, $G_{n,k}=qK_{k}\cup K_{r}$. Further, if $k\geq 3$ is an odd, $r=\left(k\pm 1\right)/2$, and $0\leq\ell <q$, $G_{n,k,\ell}=\ell K_{k}\cup\left(K_{\left(k-1\right)/2}+\overline{K_{n-k\ell -\left(k-1\right)/2}}\right)$.

Since we want to avoid the cycle of length larger than $k-1$, it seems that when removing a vertex, the new graph must avoid $P_{k-1}$. If we pick any $G\in{\rm{EX}}\left(n-1;P_{k-1}\right)$, adding a new vertex into $G$ adjacent to all other vertices gives a new graph which avoid all cycle with length larger than $k-1$. This is a possible graph for the reason that when adding any other edges, it must form a $P_{k-1}$ in the original graph $G$ and induce a cycle of length $k$. Thus, we have ${\rm{ex}}\left(n;\mathcal{C}_{k}\right)\geq {\rm{ex}}\left(n-1;P_{k-1}\right)+n-1$.

But I cannot go further to find explitity number of ${\rm{ex}}\left(n;\mathcal{C}_{k}\right)$, not to mention ${\rm{EX}}\left(n;\mathcal{C}_{k}\right)$.

Thanks in advance.