✦ LIBER ✦

Induced Circuits in Planar Graphs

✍ Scribed by C. Mcdiarmid; B. Reed; A. Schrijver; B. Shepherd

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 291 KB
Volume: 60
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1011

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Packing Odd Circuits in Eulerian Graphs

✍ James F. Geelen; Bertrand Guenin 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 179 KB

Let C be the clutter of odd circuits of a signed graph ðG; SÞ: For nonnegative integral edge-weights w; we are interested in the linear program minðw t x: xðCÞ51; for C 2 C; and x50Þ; which we denote by (P). The problem of solving the related integer program clearly contains the maximum cut problem,

2-Walks in Circuit Graphs

✍ Z.C. Gao; R.B. Richter 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 390 KB

We prove the conjecture of Jackson and Wormald that every 3-connected planar graph has a closed walk visiting every vertex once or twice. This strengthens Barnette's Theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3 . The result also holds for 3 -connected

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.

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

On removable circuits in graphs and matr

On removable circuits in graphs and matroids

✍ Lemos, Manoel; Oxley, James 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 283 KB

Mader proved that every 2-connected simple graph G with minimum degree d exceeding three has a cycle C, the deletion of whose edges leaves a 2-connected graph. Jackson extended this by showing that C may be chosen to avoid any nominated edge of G and to have length at least d-1. This article proves

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