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

Open Mathematics

Zhang Xinhong¹  Li Ruijuan² 

[1] Department of Applied Mathematics, Taiyuan University of Science and Technology, 030024 Taiyuan, People's Republic of China;School of Mathematical Sciences, Shanxi University, 030006 Taiyuan, People's Republic of China;

关键词: h-force set;    h-force number;    ore’s theorem;    weak closure;    05c07;    05c45;   

DOI  :  10.1515/math-2020-0039

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown