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\{\varepsilon(G) : G \in \mathcal{G}(n;\theta_{2k+1})\}\). In this paper, we determine \(f(n; 0_5)\), by proving that for \(n \geq 11\), \(f(n; 0_5) \leq \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).