On the Minimum Order of Extremal Graphs to have a Prescribed Girth

Abstract

We show that any n‐vertex extremal graph G without cycles of length at most k has girth exactly $k+1$ if $k\ge 6$ and $n>(2(k-2)^{k-2}+k-5)/(k-3)$. This result provides an improvement of the asymptotical known result by Lazebnik and Wang [J. Graph Theory, 26 (1997), pp. 147–153] who proved that the girth is exactly $k+1$ if $k\ge 12$ and $n\ge 2^{a^2+a+1}k^a$, where $a=k-3-\lfloor(k-2)/4\rfloor$. Moreover, we prove that the girth of G is at most $k+2$ if $n>(2(t-2)^{k-2}+t-5)/(t-3)$, where $t=\lceil (k+1)/2\rceil\ge 4$. In general, for $k\ge 5$ we show that the girth of G is at most $2k-4$ if $n\ge 2k-2$.