On Longest Cycles in Essentially 4-Connected Planar Graphs

• Autorzy: Igor Fabrici , Jochen Harant , Stanislav Jendroľ
• 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

EN

planar graph; longest cycle

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 565-575

Daty

wydano

2016-08-01

otrzymano

2015-06-16

poprawiono

2015-09-23

zaakceptowano

2015-09-23

online

2016-07-06

Twórcy

autor

Igor Fabrici

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

autor

Jochen Harant

• Institute of Mathematics Ilmenau University of Technology, Germany

autor

Stanislav Jendroľ

• 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]

Identyfikatory

DOI

10.7151/dmgt.1875