Edge-maximal -free non-bipartite Hamiltonian graphs of odd order

Abstract

Let (Formula presented.) denote the class of non-bipartite graphs on n vertices containing no (Formula presented.) -graph and (Formula presented.) Let (Formula presented.) denote the class of non-bipartite Hamiltonian graphs on n vertices containing no (Formula presented.) -graph and (Formula presented.) In this paper we determine (Formula presented.) by proving that for sufficiently large odd n, (Formula presented.) Furthermore, the bound is best possible. Our results confirm the conjecture made by Bataineh in 2007.