Edge-Maximal Graphs Without ${\theta }_5$-Graphs

Abstract

Let $G(n;{\theta }_{2k+1})$ denote the class of non-bipartite graphs on $n$ vertices containing no ${\theta }_{2k+1}$-graph and let $f(n;{\theta }_{2k+1})=max\{\epsilon (G):G\in \mathcal{G}(n;{\theta }_{2k+1})\}$. In this paper, we determine $f(n;0_5)$, by proving that for $n\ge 11$, $f(n;0_5)\le \lfloor \frac{(n-1{)}^2}{4}\rfloor +1$. Further, the bound is best possible. Our result confirms the validity of the conjecture made in [1], “Some extremal problems in graph theory”, Ph.D. thesis, Curtin University of Technology, Australia (2007).