Properties of Certain Families of 2k-Cycle-Free Graphs

Let v = v(G) and e = e(G) denote the order and size of a simple graph G, respectively. Let G = {Gi}i≥1, be a family of simple graphs of magnitude r > 1 and constant λ > 0, i.e., e(Gi) = (λ + o(1))v(Gi)r, i → ∞. For any such family G, whose members are bipartite and of girth at least 2k + 2, and every integer t, 2 ≤ t ≤ k − 1, we construct a family G̃t of graphs of the same magnitude r, of constant greater than λ, and all of whose members contain each of the cycles C4, C6, ..., C2t, but none of the cycles C2t + 2, ..., C2k. We also prove that for every family of 2k-cycle-free extremal graphs (i.e., graphs having the greatest size among all 2k-cycle-free graphs of the same order), all but finitely many such graphs must be either non-bipartite or have girth at most 2k − 2. In particular, we show that the best known lower bound on the size of 2k-cycle-free extremal graphs for k = 3, 5, namely (2 − (k + 1)/k + o(1))v(k + 1)/k, can be improved to ((k − 1)·k − (k + 1)/k + o(1))v(k + 1)/k.