Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 1 | 71-89

Tytuł artykułu

On Vertices Enforcing a Hamiltonian Cycle

Treść / Zawartość

Warianty tytułu

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

Wydawca

Rocznik

Tom

33

Numer

1

Strony

71-89

Opis fizyczny

Daty

wydano
2013-03-01
online
2013-04-13

Twórcy

autor
  • Institute of Mathematics P.J. Šafárik University in Košice, Slovak Republic
autor
  • Institut für Mathematik Technische Universität Ilmenau, Germany
  • 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]

Typ dokumentu

Bibliografia

Identyfikatory

Identyfikator YADDA

bwmeta1.element.doi-10_7151_dmgt_1653
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.