𝔖 Bobbio Scriptorium
✦   LIBER   ✦

2-Walks in Circuit Graphs

✍ Scribed by Z.C. Gao; R.B. Richter

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
390 KB
Volume
62
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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 projective planar graphs. 1994 Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

Undirected graphs rearrangeable by 2-len
Undirected graphs rearrangeable by 2-length walks
✍ Barth, Dominique; Panaite, Petri?or πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 147 KB

In this paper, we deal with 2-rearrangeable graphs, that is, graphs in which every permutation can be routed in two steps, such that each packet moves on a walk of length 2 without vertex-contention. We give necessary and sufficient conditions for a graph to be 2-rearrangeable. We end by proposing a

Induced Circuits in Planar Graphs
Induced Circuits in Planar Graphs
✍ C. Mcdiarmid; B. Reed; A. Schrijver; B. Shepherd πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 291 KB
Random walks on random simple graphs
Random walks on random simple graphs
✍ Martin Hildebrand πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 676 KB

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (logn)", where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou

Packing Odd Circuits in Eulerian Graphs
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,