✦ LIBER ✦

Spanning paths in infinite planar graphs

✍ Scribed by Dean, Nathaniel; Thomas, Robin; Yu, Xingxing

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 796 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199610)23:2<163::aid-jgt7>3.0.co;2-r

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a 4connected infinite planar graph such that the deletion of any finite set of vertices of G results in at most one infinite component. We prove a conjecture of Nash-Williams that G has a 1 -way infinite spanning path. 0 1996 John Wiley & Sons, Inc. [7] has shown that every 4-connected finite planar graph is hamiltonian. (In this paper graphs have no loops or multiple edges, but may be infinite.) To generalize Tutte's result to infinite graphs one can ask if every Cconnected infinite planar graph has a 1-way infinite spanning path, but that is clearly false. Indeed, no graph can have such a path if the deletion of some finite set of vertices leaves more than one infinite component. However, Nash-Williams [2] conjectured that this is the only way the generalization can fail. Nash-Williams' conjecture was partially confirmed by Jung [l] who proved it for triangulations. (Our thanks to R. Halin for bringing this reference to our attention.) We prove the conjecture in general, but we need some definitions before we can state our main result precisely.

INTRODUCTION

Tutte

📜 SIMILAR VOLUMES

Infinite paths in planar graphs III, 1-w

Infinite paths in planar graphs III, 1-way infinite paths

✍ Xingxing Yu 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 336 KB

An infinite graph is 2-indivisible if the deletion of any finite set of vertices from the graph results in exactly one infinite component. Let G be a 4-connected, 2-indivisible, infinite, plane graph. It is known that G contains a spanning 1-way infinite path. In this paper, we prove a stronger resu

Infinite paths in planar graphs IV, divi

Infinite paths in planar graphs IV, dividing cycles

✍ Xingxing Yu 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB 👁 1 views

Nash-Williams conjectured that a 4-connected infinite planar graph contains a spanning 2-way infinite path if, and only if, the deletion of any finite set of vertices results in at most two infinite components. In this article, we prove this conjecture for graphs with no dividing cycles and for grap

Infinite paths in planar graphs I: Graph

Infinite paths in planar graphs I: Graphs with radial nets

✍ Xingxing Yu 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB 👁 1 views

## Abstract Let __G__ be an infinite 4‐connected planar graph such that the deletion of any finite set of vertices from __G__ results in exactly one infinite component. Dean __et al__. proved that either __G__ admits a radial net or a special subgraph of __G__ admits a ladder net, and they used the

Infinite paths in planar graphs II, stru

Infinite paths in planar graphs II, structures and ladder nets

✍ Xingxing Yu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 217 KB 👁 1 views

## Abstract A graph is __k‐indivisible__, where __k__ is a positive integer, if the deletion of any finite set of vertices results in at most __k__ – 1 infinite components. In 1971, Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if and onl

On paths in planar graphs

✍ Sanders, Daniel P. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 2 views

This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary, it is shown that every 4-connected planar graph has a Hamilton path between any two specified vertices x, y and containing any specified edge other than xy.

A theorem on paths in planar graphs

✍ Norishige Chiba; Takao Nishizeki 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 1 views

C. Thomassen extended Tutte's theorem on cycles in planar graphs in the paper "A Theorem on Paths in Planar Graphs". This note corrects a flaw in his proof.