𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Short Disjoint Paths in Locally Connected Graphs

✍ Scribed by Chuanping Chen; Roman Čada; Tomáš Kaiser; Zdeněk Ryjáček

Publisher
Springer Japan
Year
2007
Tongue
English
Weight
185 KB
Volume
23
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Edge-disjoint paths and cycles in n-edge
Edge-disjoint paths and cycles in n-edge-connected graphs
✍ Andreas Huck 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 826 KB

## Abstract We consider finite undirected loopless graphs __G__ in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal __n__ ≥ 0 with the following property: If __G__ is an __n__‐edge‐connected graph, __s__~1~, ⃛,__s__~k~, __t__~1~, ⃛,__t__~k~ are vertices of __G__, a

Disjoint T-paths in tough graphs
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

Vertex-disjoint paths and edge-disjoint
Vertex-disjoint paths and edge-disjoint branchings in directed graphs
✍ R. W. Whitty 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB

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.