Removable matchings and hamiltonian cycles

AbstractFor a graph G, let σ2(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ2(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ2(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K2+(K2∪Kn−4) or G≅K2¯+(K2∪Kn−4); (ii) Let G be a graph of order n≥16k+1 with σ2(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible