Edge-maximal graphs without θ 7 -graphs

Abstract

Let G(n; θ2k+1, ≥ δ) denote the class of non-bipartite θ2k+1-free graphs on n vertices and minimum degree at least δ and let f (n; θ2k+1, ≥ δ) = max{ε(G): G ∈ G(n; θ2k+1, ≥ δ)}. In this paper we determinj an upker bound of f (n; θ7, ≥ 25) by proving that for large n, f (n; θ7, ≥ 25) ≤⌊(n-2)2/4 ⌊+ 3. Our result confirm the conjecture made in [1], "Some extermal problems in graph theory", Ph.D thesis, Curtin University of Technology, Australia (2007), in case k = 3 and δ=25. AMS 2010 Mathematics Subject Classification. Primary 05C38; Secondary 05C35.