✦ LIBER ✦

On Hamilton cycles in certain planar graphs

✍ Scribed by Sanders, Daniel P.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 586 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199601)21:1<43::aid-jgt6>3.0.co;2-m

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a 2-connected plane graph with outer cycle XG such that for every minimal vertex cut S of G with IS1 5 3, every component of G \ S contains a vertex of XG.

A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as a recent theorem of Dillencourt about NST-triangulations. A linear algorithm to find a Hamilton cycle can be extracted from the proof. One corollary is that a 4-connected planar graph with the vertices of a triangle deleted is Hamiltonian.

📜 SIMILAR VOLUMES

On certain Hamiltonian cycles in planar

On certain Hamiltonian cycles in planar graphs

✍ B�hme, T.; Harant, J.; Tk�?, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 2 views

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that mus

Hamilton Cycles in Planar Graphs and Ven

Hamilton Cycles in Planar Graphs and Venn Diagrams

✍ Kiran B. Chilakamarri; Peter Hamburger; Raymond E. Pippert 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 258 KB

Using graph theory, we prove Gru nbaum's conjecture: Every Venn diagram of n curves can be extended to a Venn diagram of n+1 curves by the addition of a suitable simple closed curve.

Hamilton cycles in regular graphs

✍ Bill Jackson 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## UNIVERSIW OF WATERLOO ' The research reported here has been sponsored by the Canadian Commonwealth Association.

Edge disjoint Hamilton cycles in graphs

✍ Guojun Li 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

Hamilton cycles in claw-free graphs

✍ Cun-Quan Zhang 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB 👁 2 views

Hamilton cycles in random graphs and dir

Hamilton cycles in random graphs and directed graphs

✍ Colin Cooper; Alan Frieze 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB 👁 3 views