✦ LIBER ✦

Five-Connected Toroidal Graphs Are Hamiltonian

✍ Scribed by Robin Thomas; Xingxing Yu

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 518 KB
Volume: 69
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1996.1713

No coin nor oath required. For personal study only.

✦ Synopsis

We prove that every edge in a 5-connected graph embedded in the torus is contained in a Hamilton cycle. Our proof is constructive and implies a polynomial time algorithm for finding a Hamilton cycle.

1997 Academic Press

On the other hand, for 4-connected graphs embedded in the torus, certain edges may not be contained in any Hamilton cycle. The following example was provided by Thomassen [8]. Embed the product of two even cycles (of length at least 4) in the torus so that every face is bounded by article no. TB961713 79 0095-8956Â97 25.00

📜 SIMILAR VOLUMES

4-Connected Projective-Planar Graphs Are

4-Connected Projective-Planar Graphs Are Hamiltonian

✍ R. Thomas; X.X. Yu 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 923 KB

All 4-connected Line Graphs of Claw Free

All 4-connected Line Graphs of Claw Free Graphs Are Hamiltonian Connected

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 109 KB

Thomassen conjectured that every 4-connected line graph is hamiltonian. Here we shall see that 4-connected line graphs of claw free graphs are hamiltonian connected.

On hamiltonian-connected graphs

✍ Ronald J. Gould; Xingxing Yu 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 735 KB

## Abstract One of the most fundamental results concerning paths in graphs is due to Ore: In a graph __G__, if deg __x__ + deg __y__ ≧ |__V__(__G__)| + 1 for all pairs of nonadjacent vertices __x, y__ ≅ __V__(__G__), then __G__ is hamiltonian‐connected. We generalize this result using set degrees.

Claw-free 3-connected P11-free graphs ar

Claw-free 3-connected P11-free graphs are hamiltonian

✍ Tomasz Łuczak; Florian Pfender 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

## Abstract We show that every 3‐connected claw‐free graph which contains no induced copy of __P__~11~ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of __P__~12~ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph T

3-Connected line graphs of triangular gr

3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian

✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

A graph is k-triangular if each edge is in at least k triangles. Triangular is a synonym for l-triangular. It is shown that the line graph of a triangular graph of order at least 4 is panconnected if and only if it is 3-connected. Furthermore, the line graph of a k-triangular graph is k-harniltonian

On Hamiltonian-connected regular graphs

✍ Ioan Tomescu 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

In this paper it is shown that any rn-regular graph of order 2rn (rn 3 3), not isomorphic to K, , , , or of order 2rn + 1 (rn even, rn 3 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains at least rn Hamiltonian