𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the problem of finding disjoint cycles and dicycles in a digraph

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

Publisher
Springer-Verlag
Year
2011
Tongue
English
Weight
372 KB
Volume
31
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Disjoint Cycles in Eulerian Digraphs and
Disjoint Cycles in Eulerian Digraphs and the Diameter of Interchange Graphs
✍ Richard A. Brualdi; Jian Shen 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 87 KB

denote the set of all m × n {0, 1}-matrices with row sum vector R and column sum vector S. Suppose A(R, S) ] ". The interchange graph G(R, S) of A(R, S) was defined by Brualdi in 1980. It is the graph with all matrices in A(R, S) as its vertices and two matrices are adjacent provided they differ by

What is the smallest number of dicycles
What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?
✍ Nathaniel Dean 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 408 KB

A digraph D with n vertices is said to be decomposable into a set S of dicycles if every arc of D is contained in exactly one member of S. Counterexamples are given to the following conjectures which are generalizations of three well-known conjectures by G. Hajos, P. Erdos, and P. J. Kelly: (1) [B.

Disjoint Cycles in Directed Graphs on th
Disjoint Cycles in Directed Graphs on the Torus and the Klein Bottle
✍ G.L. Ding; A. Schrijver; P.D. Seymour 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 203 KB

We give necessary and sufficient conditions for a directed graph embedded on the torus or the Klein bottle to contain pairwise disjoint circuits, each of a given orientation and homotopy, and in a given order. For the Klein bottle, the theorem is new. For the torus, the theorem was proved before by

On the existence of a specified cycle in
On the existence of a specified cycle in digraphs with constraints on degrees
✍ Abdelhamid Benhocine 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

We prove that Woodall's and GhouileHouri's conditions on degrees which ensure that a digraph is Hamiltonian, also ensure that it contains the analog of a directed Hamiltonian cycle but with one edge pointing the wrong way; that is, it contains two vertices that are connected in the same direction by