On the girth of extremal graphs without shortest cycles

Let EX(v; {C-3, ...... C-n}) denote the set of graphs G of order v that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n + 1 cycle? We prove that the diameter of G is at most n - 1, and present several results concerning the above question: the girth of G is g = n + 1 if (i) v >= n + 5, diameter equal to n - 1 and minimum degree at least 3; (ii) v >= 12, v is not an element of{15, 80, 170} and n = 6. Moreover, if v = 15 we find an extremal graph of girth 8 obtained front a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if v >= 2n - 3 and n >= 7 the girth is at most 2n - 5. We also show that the answer to the question is negative for v <= n + 1 + [(n - 2)/2]. (C) 2007 Elsevier B.V. All rights reserved.