✦ LIBER ✦

Infinite paths in planar graphs I: Graphs with radial nets

✍ Scribed by Xingxing Yu

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 234 KB
Volume: 47
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20028

No coin nor oath required. For personal study only.

✦ Synopsis

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 these nets to show that G contains a spanning 1‐way infinite path. In this paper, we show that if G admits a radial net, then G also contains a spanning 2‐way infinite path. This is a step towards a conjecture of Nash‐Williams. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 147–162, 2004

📜 SIMILAR VOLUMES

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

Spanning paths in infinite planar graphs

✍ Dean, Nathaniel; Thomas, Robin; Yu, Xingxing 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 796 KB

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 fini

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