Edge maximal non-bipartite Hamiltonian graphs without theta graphs of order 7

Abstract

For a set of graphs \(\mathcal{F}\), let \(\mathcal{H}(n;\mathcal{F})\) denote the class of non-bipartite Hamiltonian graphs on n vertices that does not contain any graph of \(\mathcal{F}\) as a subgraph and \(h(n;\mathcal{F}) \; = \; max\{\mathcal{E}(G) : G ∈ \mathcal{H}(n;\mathcal{F})\}\) where \(\mathcal{E}(G)\) is the number of edges in G.  In this paper, we determine h(n; {θ₄, θ₅, θ₇}) and we establish an upper bound of h(n; θ₇) for sufficiently even large n.  Our results confirms the conjecture made in [1] for k = 3.