On Vertices Enforcing a Hamiltonian Cycle

Igor Fabrici; Erhard Hexel; Stanislav Jendrol’

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 71-89
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Igor Fabrici, Erhard Hexel, and Stanislav Jendrol’. "On Vertices Enforcing a Hamiltonian Cycle." Discussiones Mathematicae Graph Theory 33.1 (2013): 71-89. <http://eudml.org/doc/267730>.

@article{IgorFabrici2013,
abstract = {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.},
author = {Igor Fabrici, Erhard Hexel, Stanislav Jendrol’},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {cycle; hamiltonian; 1-hamiltonian; Hamiltonian; 1-Hamiltonian},
language = {eng},
number = {1},
pages = {71-89},
title = {On Vertices Enforcing a Hamiltonian Cycle},
url = {http://eudml.org/doc/267730},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Igor Fabrici
AU - Erhard Hexel
AU - Stanislav Jendrol’
TI - On Vertices Enforcing a Hamiltonian Cycle
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 71
EP - 89
AB - 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.
LA - eng
KW - cycle; hamiltonian; 1-hamiltonian; Hamiltonian; 1-Hamiltonian
UR - http://eudml.org/doc/267730
ER -

References

top
  1. [1] C.A. Barefoot, Hamiltonian connectivity of the Halin graphs, Congr. Numer. 58 (1987) 93-102. Zbl0649.05047
  2. [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. [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] Zbl0492.05049
  4. [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] Zbl0656.05045
  5. [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. [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. [7] G. Chartrand and L. Lesniak, Graphs & Digraphs (Chapman & Hall, 2005). Zbl1057.05001
  8. [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] Zbl0608.05048
  9. [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. [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] Zbl0096.17903
  11. [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] Zbl0090.39401
  12. [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] Zbl0256.05121
  13. [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] Zbl1229.05169
  14. [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] Zbl0546.05039
  15. [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. [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] Zbl0299.05101
  17. [17] D.A. Nelson, Hamiltonian graphs, Master Thesis (Vanderbilt University, 1973). 
  18. [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] Zbl0424.05036
  19. [19] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27. Zbl0106.37103
  20. [20] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176. doi:10.1002/jgt.3190070205[Crossref] 
  21. [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] Zbl0070.18403
  22. [22] T. Zamfirescu, Three small cubic graphs with interesting hamiltonian properties, J. Graph Theory 4 (1980) 287-292. doi:10.1002/jgt.3190040306[Crossref] Zbl0442.05047

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.