New families of graphs without short cycles and large size
We denote by ex(n;{C3,C4,,Cs}) e x ( n ; { C 3 , C 4 ,  , C s } ) or fs(n) f s ( n ) the maximum number of edges in a graph of order n n and girth at least s+1 s + 1 . First we give a method to transform an n n -vertex graph of girth g g into a graph of girth at least g?1 g ? 1 on fewer vertices. For an infinite sequence of values of n n and s?{4,6,10} s ? { 4 , 6 , 10 } the obtained graphs are denser than the known constructions of graphs of the same girth s+1 s + 1 . We also give another different construction of dense graphs for an infinite sequence of values of n n and s?{7,11} s ? { 7 , 11 } . These two methods improve the known lower bounds on fs(n) f s ( n ) for s?{4,6,7,10,11} s ? { 4 , 6 , 7 , 10 , 11 } which were obtained using different algorithms. Finally, to know how good are our results, we have proved that lim sup n ? ? f s ( n ) n 1 + 2 s ? 1 = 2 ? 1 ? 2 s ? 1 for s?{5,7,11} s ? { 5 , 7 , 11 } , and s ? 1 ? 2 s ? lim sup n ? ? f s ( n ) n 1 + 2 s ? 0.5 for s?{6,10} s ? { 6 , 10 } .
extremal graph cages extremal function