PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 565-575
Tytuł artykułu

On Longest Cycles in Essentially 4-Connected Planar Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover, new lower bounds on the length of a longest cycle of G are presented if G is an essentially 4-connected planar graph of maximum degree 4 or G is an essentially 4-connected maximal planar graph.
Słowa kluczowe
Wydawca
Rocznik
Tom
36
Numer
3
Strony
565-575
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2015-06-16
poprawiono
2015-09-23
zaakceptowano
2015-09-23
online
2016-07-06
Twórcy
autor
  • Institute of Mathematics P.J. Šafárik University in Košice, Slovakia
  • Institute of Mathematics Ilmenau University of Technology, Germany
  • Institute of Mathematics P.J. Šafárik University in Košice, Slovakia
Bibliografia
  • [1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
  • [2] I. Fabrici, J. Harant and S. Jendroľ, Paths of low weight in planar graphs, Discuss. Math. Graph Theory 28 (2008) 121-135. doi:10.7151/dmgt.1396[Crossref]
  • [3] B. Grünbaum and J. Malkevitch, Pairs of edge-disjoint Hamilton circuits, Aequationes Math. 14 (1976) 191-196. doi:10.1007/BF01836218[Crossref]
  • [4] B. Jackson and N.C. Wormald, Longest cycles in 3-connected planar graphs, J. Combin. Theory Ser. B 54 (1992) 291-321. doi:10.1016/0095-8956(92)90058-6[Crossref]
  • [5] D.P. Sanders, On paths in planar graphs, J. Graph Theory 24 (1997) 341-345. doi:10.1002/(SICI)1097-0118(199704)24:4<341::AID-JGT6>3.0.CO;2-O[Crossref]
  • [6] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176. doi:10.1002/jgt.3190070205[Crossref]
  • [7] 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]
  • [8] C.-Q. Zhang, Longest cycles and their chords, J. Graph Theory 11 (1987) 521-529. doi:10.1002/jgt.3190110409[Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1875
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ć.