- Tytuł:
- Longer Cycles in Essentially 4-Connected Planar Graphs
- Autorzy:
-
Fabrici, Igor
Harant, Jochen
Mohr, Samuel
Schmidt, Jens M. - Tematy:
-
essentially 4-connected planar graph
longest cycle
circumference
shortness coefficient - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/32083770.pdf Link otwiera się w nowym oknie
- Opis:
- 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 $ \text{circ} (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 $ \text{circ} (G) \ge 1/2 (n+4) $. In the present paper, we prove that an essentially 4-connected planar graph on $n$ vertices contains a cycle of length at least $ 3/5 (n+2) $ and that such a cycle can be found in time $ O(n^2) $.
- Dostawca treści:
- Biblioteka Nauki
Artykuł