Longer cycles in essentially 4-connected planar graphs

I Fabrici, J Harant, S Mohr, JM Schmidt - arXiv preprint arXiv:1710.05619, 2017 - arxiv.org
A planar 3-connected graph $ G $ is called\emph {essentially $4 $-connected} if, for every 3-
separator $ S $, at least one of the two components of $ GS $ is an isolated vertex. Jackson
and Wormald proved that the length $\mathop {\rm circ}\nolimits (G) $ of a longest cycle of
any essentially 4-connected planar graph $ G $ on $ n $ vertices is at least $\frac {2n+ 4}{5}
$ and Fabrici, Harant and Jendrol'improved this result to $\mathop {\rm circ}\nolimits
(G)\geq\frac {1}{2}(n+ 4) $. In the present paper, we prove that an essentially 4-connected …

[PDF][PDF] Longer cycles in essentially 4-connected planar graphs

S Mohr - Dear Participant - umv.science.upjs.sk
A planar 3-connected graph G is called essentially 4-connected if, for every 3-separator S, at
least one of the two components of G− S is an isolated vertex. Jackson and Wormald proved
that the length circ (G) of a longest cycle of any essentially 4-connected planar graph on n
vertices is at least 2n+ 4
以上显示的是最相近的搜索结果。 查看全部搜索结果