𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Disjoint T-paths in tough graphs

✍ Scribed by Tomáš Kaiser

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
120 KB
Volume
59
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 graphs that are tough (the removal of any nonempty set X of vertices yields at most |X| components), we completely characterize the edges that are contained in some T‐path covering. Our main tool is Mader's ${\cal S}$‐paths theorem. A corollary of our result is that each edge of a k‐regular k‐edge‐connected graph (k ≥ 2) is contained in a T‐path covering. This is, in a sense, a best possible counterpart of the result of Plesník that every edge of a k‐regular (k‐1)‐edge‐connected graph of even order is contained in a 1‐factor. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 1–10, 2008

📜 SIMILAR VOLUMES

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.

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

How many disjoint 2-edge paths must a cu
How many disjoint 2-edge paths must a cubic graph have?
✍ Alexander Kelmans; Dhruv Mubayi 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB

## Abstract In this paper we show that every simple cubic graph on __n__ vertices has a set of at least ⌈ __n__/4 ⌉ disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Gra