The H-force sets of the graphs satisfying the condition of Ore’s theorem

Abstract

Let G be a Hamiltonian graph. A nonempty vertex set X⊆V(G)X\subseteq V(G) is called a Hamiltonian cycle enforcing set (in short, an H-force set) of G if every X-cycle of G (i.e., a cycle of G containing all vertices of X) is a Hamiltonian cycle. For the graph G, h(G)h(G) (called the H-force number of G) is the smallest cardinality of an H-force set of G. Ore’s theorem states that an n-vertex graph G is Hamiltonian if d(u)+d(v)≥nd(u)+d(v)\ge n for every pair of nonadjacent vertices u,vu,v of G. In this article, we study the H-force sets of the graphs satisfying the condition of Ore’s theorem, show that the H-force number of these graphs is possibly n, or n−2n-2, or n2\frac{n}{2} and give a classification of these graphs due to the H-force number.

Keywords

• h-force set
• h-force number
• ore’s theorem
• weak closure
• 05c07
• 05c45