✦ LIBER ✦

Hamilton cycles in plane triangulations

✍ Scribed by Bill Jackson; Xingxing Yu

Publisher: John Wiley and Sons
Year: 2002
Tongue: English
Weight: 134 KB
Volume: 41
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10057

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002

📜 SIMILAR VOLUMES

Simultaneous diagonal flips in plane tri

Simultaneous diagonal flips in plane triangulations

✍ Prosenjit Bose; Jurek Czyzowicz; Zhicheng Gao; Pat Morin; David R. Wood 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 468 KB

## Abstract Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with __n__ ≥ 6 vertices has a simultaneous flip into a 4‐connected triangulation, and that the set of edges to be flipped can be computed in $\cal O$(__n__) time. It follows that

Hamilton cycles in prisms

✍ Tomáš Kaiser; Zdeněk Ryjáček; Daniel Král; Moshe Rosenfeld; Heinz-Jürgen Voss 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB

## Abstract The prism over a graph __G__ is the Cartesian product __G__ □ __K__~2~ of __G__ with the complete graph __K__~2~. If __G__ is hamiltonian, then __G__□__K__~2~ is also hamiltonian but the converse does not hold in general. Having a hamiltonian prism is shown to be an interesting relaxati

Oriented hamilton cycles in digraphs

✍ Roland Häggkvist; Andrew Thomason 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 473 KB

## Abstract We show that a directed graph of order __n__ will contain __n__‐cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 + __n__^‐1/6^)__n__ and __n__ is sufficiently large. © 1995 John Wiley & Sons, Inc.

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.

On the number of Hamiltonian cycles in t

On the number of Hamiltonian cycles in triangulations

✍ Jan Kratochvil; Dainis Zeps 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

It is proved that if a planar triangulation different from K3 and K4 contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [21, this yields that, for n 2 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar

Edge disjoint Hamilton cycles in graphs

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