Geodesic
On Vertices Enforcing a Hamiltonian Cycle
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 71-89.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: cycle, hamiltonian, 1-hamiltonian 
@article{DMGT_2013_33_1_a6,
     author = {Fabrici, Igor and Hexel, Erhard and Jendrol{\textquoteright}, Stanislav},
     title = {On {Vertices} {Enforcing} a {Hamiltonian} {Cycle}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {71--89},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a6/}
}
TY  - JOUR
AU  - Fabrici, Igor
AU  - Hexel, Erhard
AU  - Jendrol’, Stanislav
TI  - On Vertices Enforcing a Hamiltonian Cycle
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 71
EP  - 89
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a6/
LA  - en
ID  - DMGT_2013_33_1_a6
ER  - 
%0 Journal Article
%A Fabrici, Igor
%A Hexel, Erhard
%A Jendrol’, Stanislav
%T On Vertices Enforcing a Hamiltonian Cycle
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 71-89
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a6/
%G en
%F DMGT_2013_33_1_a6
Fabrici, Igor; Hexel, Erhard; Jendrol’, Stanislav. On Vertices Enforcing a Hamiltonian Cycle. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 71-89. http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a6/

[1] C.A. Barefoot, Hamiltonian connectivity of the Halin graphs, Congr. Numer. 58 (1987) 93-102.

[2] J.A. Bondy, Pancyclic graphs: recent results, in: Infinite and finite sets, Vol. 1, Colloq. Math. Soc. János 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

[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

[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

[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

[7] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman & Hall, 2005).

[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

[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

[10] G.A. Dirac, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Math. Nachr. 22 (1960) 61-85. doi:10.1002/mana.19600220107

[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

[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

[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

[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

[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

[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

[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

[19] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27.

[20] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176. doi:10.1002/jgt.3190070205

[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

[22] T. Zamfirescu, Three small cubic graphs with interesting hamiltonian properties, J. Graph Theory 4 (1980) 287-292. doi:10.1002/jgt.3190040306