On Vertices Enforcing a Hamiltonian Cycle

• Autorzy: Igor Fabrici , Erhard Hexel , Stanislav Jendrol’
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cycle; hamiltonian; 1-hamiltonian

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 1
• Strony: 71-89

Daty

wydano

2013-03-01

online

2013-04-13

Twórcy

autor

Igor Fabrici

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

autor

Erhard Hexel

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

autor

Stanislav Jendrol’

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

Bibliografia

• [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´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]
• [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]
• [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).
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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[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]
• [22] T. Zamfirescu, Three small cubic graphs with interesting hamiltonian properties, J. Graph Theory 4 (1980) 287-292. doi:10.1002/jgt.3190040306[Crossref]

Identyfikatory

DOI

10.7151/dmgt.1653