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

Abstract

For a set of graphs F, let H(n; F) denote the class of non-bipartite Hamiltonian graphs on n vertices that does not contain any graph of F as a subgraph and h(n; F) = max{E(G): G ? H(n; F)} where E(G) is the number of edges in G. In this paper, we determine h(n; {?4, ?5, ?7}) and we establish an upper bound of h(n; ?7) for sufficiently even large n. Our results confirms the conjecture made in [1] for k = 3. - 2019 Forum-Editrice Universitaria Udinese SRL. All rights reserved.