✦ LIBER ✦

Vertex-disjoint paths and edge-disjoint branchings in directed graphs

✍ Scribed by R. W. Whitty

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 482 KB
Volume: 11
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190110309

No coin nor oath required. For personal study only.

✦ Synopsis

A theorem of J. Edmonds states that a directed graph has k edge-disjoint branchings rooted at a vertex r if and only if every vertex has k edge-disjoint paths to r . We conjecture an extension of this theorem to vertex-disjoint paths and give a constructive proof of the conjecture in the case k = 2.

📜 SIMILAR VOLUMES

Edge-disjoint cycles in regular directed

Edge-disjoint cycles in regular directed graphs

✍ Alon, Noga; McDiarmid, Colin; Molloy, Michael 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB 👁 3 views

We prove that any k-regular directed graph with no parallel edges contains a collection of at least fl(k2) edge-disjoint cycles; we conjecture that in fact any such graph contains a collection of at least ( lCi1 ) disjoint cycles, and note that this holds for k 5 3. o 1996

Edge disjoint cycles in graphs

✍ Li Hao 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 419 KB

Disjoint T-paths in tough graphs

✍ Tomáš Kaiser 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB

## Abstract Let __G__ be a graph and __T__ a set of vertices. A __T‐path__ in __G__ is a path that begins and ends in __T__, and none of its internal vertices are contained in __T__. We define a __T‐path covering__ to be a union of vertex‐disjoint __T__‐paths spanning all of __T__. Concentrating on

Polynomial time algorithm for constructi

Polynomial time algorithm for constructing vertex-disjoint paths in transposition graphs

✍ Satoshi Fujita 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 415 KB

Edge disjoint Hamilton cycles in graphs

✍ Guojun Li 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

Edge-Disjoint (s, t)-Paths in Undir

Edge-Disjoint (s, t)-Paths in Undirected Planar Graphs in Linear Time

✍ Karsten Weihe 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 279 KB

We consider the following problem. Let G s V, E be an undirected planar graph and let s, t g V, s / t. The problem is to find a set of pairwise edge-disjoint paths in G, each connecting s with t, of maximum cardinality. In other words, the problem is to find a maximum unit flow from s to t. The fast