✦ LIBER ✦

Note on a min-max conjecture of Woodall

✍ Scribed by Orlando Lee; Yoshiko Wakabayashi

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 78 KB
Volume: 38
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.1022

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In 1978 Woodall [6] conjectured the following: in a planar digraph the size of a shortest cycle is equal to the maximum cardinality of a collection of disjoint tranversals of cycles. We prove that this conjecture is true when the digraph is series‐parallel. In fact, we prove a stronger weighted version that gives the latter result as a corollary. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 36–41, 2001

📜 SIMILAR VOLUMES

On a Conjecture of Woodall

✍ Hao Li 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 164 KB

Dirac proved in 1952 that every 2-connected graph of order n and minimum degree k admits a cycle of length at least minfn; 2kg: As a possible improvement, Woodall conjectured in 1975 that if a 2-connected graph of order n has at least n 2 þ k vertices of degree at least k; then it has a cycle of len

A note on the abc conjecture

✍ Pei-Chu Hu; Chung-Chun Yang 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 187 KB

A Note on Alperin′s Conjecture

✍ G.R. Robinson 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 147 KB

Solving min-max shortest-path problems o

Solving min-max shortest-path problems on a network

✍ Ishwar Murthy; Shenq-Shyong Her 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 877 KB

In this article we consider the problem of determining a path between two nodes in a network that minimizes the maximum of r path length values associated with it. This problem has a direct application in scheduling. It also has indirect applications in a class of routing problems and when consideri

A note on possible extensions of Negami'

A note on possible extensions of Negami's conjecture

✍ Hlin?n�, Petr 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 2 views

A graph H is a cover of a graph G, if there exists a mapping ϕ from V (H) onto V (G) such that for every vertex v of G, ϕ maps the neighbors of v in H bijectively onto the neighbors of ϕ(v) in G. Negami conjectured in 1987 that a connected graph has a finite planar cover if and only if it embeds in

A Note on Fisher's Inequality

✍ Douglas R. Woodall 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 226 KB

A new proof is given of the nonuniform version of Fisher's inequality, first proved by Majumdar. The proof is ``elementary,'' in the sense of being purely combinatorial and not using ideas from linear algebra. However, no nonalgebraic proof of the n-dimensional analogue of this result (Theorem 3 her