×

The H-force sets of the graphs satisfying the condition of Ore’s theorem. (English) Zbl 1475.05032

Summary: Let \(G\) be a Hamiltonian graph. A nonempty vertex set \(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) (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)\ge n\) for every pair of nonadjacent vertices \(u,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-2\), or \(\frac{n}{2}\) and give a classification of these graphs due to the H-force number.

MSC:

05C07 Vertex degrees
05C45 Eulerian and Hamiltonian graphs

References:

[1] John Adrian Bondy and Uppaluri Siva Ramachandra Murty, Graph Theory With Application, Springer, New York, 2007.
[2] Shengjia Li, Ruijuan Li, and Jinfeng Feng, An efficient condition for a graph to be Hamiltonian, Discrete Appl. Math. 155 (2007), no. 14, 1842-1845, . · Zbl 1123.05060 · doi:10.1016/j.dam.2007.03.013
[3] Ronald J. Gould, Updating the Hamiltonian problem – a survey, J. Graph Theory 15 (1991), no. 2, 121-157, . · Zbl 0746.05039 · doi:10.1002/jgt.3190150204
[4] Ronald J. Gould, Advances on the Hamiltonian problem – a survey, Graph Combin. 19 (2003), 7-52, . · Zbl 1024.05057 · doi:10.1007/s00373-002-0492-x
[5] Genghua Fan, New sufficient conditions for cycles in graph, J. Combin. Theory Ser. B 37 (1984), no. 3, 221-227, . · Zbl 0551.05048 · doi:10.1016/0095-8956(84)90054-6
[6] Igor Fabrici, Erhard Hexel, and Stanislav Jendro’, On vertices enforcing a hamiltonian cycle, Discuss. Math. Graph Theory 33 (2013), no. 1, 71-89, . · Zbl 1293.05205 · doi:10.7151/dmgt.1653
[7] Xinhong Zhang, Ruijuan Li, and Shengjia Li, H-force sets of locally semicomplete digraphs, Discrete Appl. Math. 160 (2012), no. 16-17, 2491-2496, . · Zbl 1251.05068 · doi:10.1016/j.dam.2012.06.014
[8] Ruijuan Li, Xinhong Zhang, Shengjia Li, Qiaoping Guo, and Yubao Guo, The H-force set of a hypertournament, Discrete Appl. Math. 169 (2014), 168-175, . · Zbl 1288.05118 · doi:10.1016/j.dam.2013.12.020
[9] Oystein Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960), no. 1, 55, . · Zbl 0089.39505 · doi:10.2307/2308928
[10] Gabriel Andrew Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. s3-2 (1952), no. 1, 69-81, . · Zbl 0047.17001 · doi:10.1112/plms/s3-2.1.69
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.