𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Disjoint directed and undirected paths and cycles in digraphs

✍ Scribed by Jørgen Bang-Jensen; Matthias Kriesell

Book ID
108281584
Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
690 KB
Volume
410
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Arc-Disjoint Paths in Expander Digraphs
Arc-Disjoint Paths in Expander Digraphs
✍ Bohman, Tom; Frieze, Alan 📂 Article 📅 2003 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 235 KB
On cycles and paths in digraphs
On cycles and paths in digraphs
✍ M.C. Heydemann 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 273 KB

The purpose of this communication is to announce some slrfficient conditions on degrees and number of arcs to insure the existence of cycles and paths in directed graphs. We show that these results are the best possible. The proofs of the theorems can be found in [4].

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.

Paths and cycles in extended and decompo
Paths and cycles in extended and decomposable digraphs
✍ Jørgen Bang-Jensen; Gregory Gutin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 835 KB

We consider digraphs --called extended locally semicomplete digraphs, or extended LSD's, for short --that can be obtained from locally semicomplete digraphs by substituting independent sets for vertices. We characterize Hamiltonian extended LSD's as well as extended LSD's containing Hamiltonian path

Tools for studying paths and cycles in d
Tools for studying paths and cycles in digraphs
✍ Delorme, C.; Ordaz, O.; Quiroz, D. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB

The main goal of this work was to describe the basic elements constituting a specialized knowledge base in the field of paths and circuits in digraphs. This knowledge base contains commented on examples with textual and graphical descriptions, invariants, relations among invariants, and theorems. It