On Longest Cycles in Essentially 4-Connected Planar Graphs

Igor Fabrici; Jochen Harant; Stanislav Jendroľ

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 565-575
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Igor Fabrici, Jochen Harant, and Stanislav Jendroľ. "On Longest Cycles in Essentially 4-Connected Planar Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 565-575. <http://eudml.org/doc/285784>.

@article{IgorFabrici2016,
abstract = {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.},
author = {Igor Fabrici, Jochen Harant, Stanislav Jendroľ},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {planar graph; longest cycle},
language = {eng},
number = {3},
pages = {565-575},
title = {On Longest Cycles in Essentially 4-Connected Planar Graphs},
url = {http://eudml.org/doc/285784},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Igor Fabrici
AU - Jochen Harant
AU - Stanislav Jendroľ
TI - On Longest Cycles in Essentially 4-Connected Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 565
EP - 575
AB - 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.
LA - eng
KW - planar graph; longest cycle
UR - http://eudml.org/doc/285784
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). 
  2. [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] Zbl1155.05010
  3. [3] B. Grünbaum and J. Malkevitch, Pairs of edge-disjoint Hamilton circuits, Aequationes Math. 14 (1976) 191-196. doi:10.1007/BF01836218[Crossref] Zbl0331.05118
  4. [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] Zbl0696.05031
  5. [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. [6] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176. doi:10.1002/jgt.3190070205[Crossref] 
  7. [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] Zbl0070.18403
  8. [8] C.-Q. Zhang, Longest cycles and their chords, J. Graph Theory 11 (1987) 521-529. doi:10.1002/jgt.3190110409[Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.