PDF

Discussiones Mathematicae Graph Theory 33(1) (2013) 71-89
DOI: https://doi.org/10.7151/dmgt.1653

Dedicated to Mietek Borowiecki on the occasion of his 70^th birthday.

On Vertices Enforcing a Hamiltonian Cycle

Igor Fabrici Institute of Mathematics P.J. Šafárik University in Košice, Slovak Republic

Erhard Hexel Institut für Mathematik Technische Universität Ilmenau, Germany

Stanislav Jendrol' Institut of Mathematics P.J. Šafárik University in Košice, Slovak Republic

Abstract

A nonempty vertex set X ⊆ V(G) of a hamiltonian graph G is called an of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The 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

2010 Mathematics Subject Classification: 05C45.

References

[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, ed(s), A. Hajnal, R. Rado and V.T. Só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.

Received 19 April 2012
Accepted 25 October 2012