Edge-Maximal Graphs Without θ2k+1-Graphs

Abstract

Let σ(n; θ2k+1) denote the class of non-bipartite graphs on n vertices having no θ2k+1- graph and f(n; θ2k+1) = max{ ε(G): G ∊ σ (n; θ2k+1)}. In this paper we determine f(n; θ2k+1), by proving that for k ≥ 4 and n ≥ 36k. Further, the bound is best possible. Our result confirms the conjecture made by Bataineh in his Ph.D. thesis “Some extremal problems in graph theory”, Curtin University of Technology, Australia (2007), for large n.