Girth of {C3, ... , Cs}-free extremal graphs

Let G be a {C-3,C- ... , C-s}-free graph with as many edges as possible. In this paper we consider a question studied by several authors, the compulsory existence of the cycle Cs+1 in G. The answer has already been proved to be affirmative for s = 3.4. 5, 6. In this work we show that the girth of G is g(G) = s + 1 when the order of G is at least 1 + s(s-2/2)(s-2) -4/s-4 if s is even, 1 + (s-1)(3)((s-2)(2) - 1/4) (s-3/2) -8s/2(s-2)(2) - 10 if s is odd. This bound is an improvement of the best general result so far known. Moreover, we also prove in the case s = 7 that the girth is g(G) = 8 for order at least 14 and characterize all the extremal graphs whose girth is not 8. (C) 2012 Elsevier B.V. All rights reserved.