Temat: 4-connected planar graph

Skocz do pozycji: 1.

Tytuł:: A New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected
Autorzy:: Lu, Xiaoyun
West, Douglas B.
Tematy:: 4-connected planar graph
Hamiltonian-connected
Tutte-path; Pokaż więcej
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Powiązania:: https://bibliotekanauki.pl/articles/31340879.pdf Link otwiera się w nowym oknie
Opis:: We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

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ł

Informacja