A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.
@article{bwmeta1.element.doi-10_7151_dmgt_1653,
author = {Igor Fabrici and Erhard Hexel and Stanislav Jendrol'},
title = {On Vertices Enforcing a Hamiltonian Cycle},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {71-89},
zbl = {1293.05205},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1653}
}
Igor Fabrici; Erhard Hexel; Stanislav Jendrol’. On Vertices Enforcing a Hamiltonian Cycle. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 71-89. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1653/
[1] C.A. Barefoot, Hamiltonian connectivity of the Halin graphs, Congr. Numer. 58 (1987) 93-102. | Zbl 0649.05047
[2] J.A. Bondy, Pancyclic graphs: recent results, in: Infinite and finite sets, Vol. 1, Colloq. Math. Soc. J´anos Bolyai 10, A. Hajnal, R. Rado and V.T. S´os (Ed(s)), (North Holland, 1975) 181-187.
[3] J.A. Bondy and L. Lovász, Cycles through specified vertices of a graph, Combinatorica 1 (1981) 117-140. doi:10.1007/BF02579268[Crossref] | Zbl 0492.05049
[4] H.J. Broersma and H.J. Veldman, 3-connected line graphs of triangular graphs are panconnected and 1-hamiltonian, J. Graph Theory 11 (1987) 399-407. doi:10.1002/jgt.3190110314[Crossref] | Zbl 0656.05045
[5] G. Chartrand, A.M. Hobbs, H.A. Jung, S.F. Kapoor, D.R. Link and C.St.J.A. Nash- Williams, The square of a block is hamiltonian connected, J. Combin. Theory. (B) 16 (1974) 290-292. doi:10.1016/0095-8956(74)90075-6[Crossref]
[6] G. Chartrand, S.F. Kapoor and D.R. Link, n-hamiltonian graphs, J. Combin. Theory 9 (1970) 308-312. doi:10.1016/S0021-9800(70)80069-2[Crossref]
[7] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman & Hall, 2005). | Zbl 1057.05001
[8] N. Chiba and T. Nishizeki, A theorem on paths in planar graphs, J. Graph Theory 10 (1986) 449-450. doi:10.1002/jgt.3190100404[Crossref] | Zbl 0608.05048
[9] V. Chvátal and P. Erdős, A note on hamiltonian circuits, Discrete Math. 2 (1972) 111-113. doi:10.1016/0012-365X(72)90079-9[Crossref]
[10] G.A. Dirac, In abstrakten Graphen vorhandene vollst¨andige 4-Graphen und ihre Unterteilungen, Math. Nachr. 22 (1960) 61-85. doi:10.1002/mana.19600220107[Crossref] | Zbl 0096.17903
[11] P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959) 337-356. doi:10.1007/BF02024498[Crossref] | Zbl 0090.39401
[12] H. Fleischner, The square of every two-connected graph is hamiltonian, J. Combin. Theory (B) 16 (1974) 29-34. doi:10.1016/0095-8956(74)90091-4[Crossref] | Zbl 0256.05121
[13] R. Gould, A look at cycles containing specified elements of a graph, Discrete Math. 309 (2009) 6299-6311. doi:10.1016/j.disc.2008.04.017[Crossref][WoS] | Zbl 1229.05169
[14] S.V. Kanetkar and P.R. Rao, Connected, locally 2-connected, K1,3-free graphs are panconnected, J. Graph Theory 8 (1984) 347-353. doi:10.1002/jgt.3190080302[Crossref] | Zbl 0546.05039
[15] K. Kawarabayashi, Cycles through a prescribed vertex set in n-connected graph, J. Combin. Theory B 90 (2004) 315-323. doi:10.1016/j.jctb.2003.08.002[Crossref]
[16] L. Lovász and M.D. Plummer, On a family of planar bicritical graphs, Proc. London Math. Soc. 30 (1975) 160-176. doi:10.1112/plms/s3-30.2.160[Crossref] | Zbl 0299.05101
[17] D.A. Nelson, Hamiltonian graphs, Master Thesis (Vanderbilt University, 1973).
[18] D.J. Oberly and D.P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is hamiltonian, J. Graph Theory 3 (1979) 351-356. doi:10.1002/jgt.3190030405[Crossref] | Zbl 0424.05036
[19] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27. | Zbl 0106.37103
[20] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176. doi:10.1002/jgt.3190070205[Crossref]
[21] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99-116. doi:10.1090/S0002-9947-1956-0081471-8[Crossref] | Zbl 0070.18403
[22] T. Zamfirescu, Three small cubic graphs with interesting hamiltonian properties, J. Graph Theory 4 (1980) 287-292. doi:10.1002/jgt.3190040306[Crossref] | Zbl 0442.05047