✦ LIBER ✦

Cycle packings in graphs and digraphs

✍ Scribed by Jennifer J. Quinn

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 196 KB
Volume: 149
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00244-q

No coin nor oath required. For personal study only.

✦ Synopsis

A cycle packing in a (directed) multigraph is a vertex disjoint collection of (directed) elementary cycles. If D is a demiregular multidigraph we show that the arcs of D can be partitioned into Ai. cycle packings --where Ain is the maximum indegree of a vertex in D. We then show that the maximum length cycle packings in any digraph contain a common vertex.

📜 SIMILAR VOLUMES

Packing Cycles in Graphs

✍ Guoli Ding; Wenan Zang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 267 KB

Hamiltonian cycles and paths in Cayley g

Hamiltonian cycles and paths in Cayley graphs and digraphs — A survey

✍ Stephen J. Curran; Joseph A. Gallian 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 927 KB

Cayley graphs arise naturally in computer science, in the study of word-hyperbolic groups and automatic groups, in change-ringing, in creating Escher-like repeating patterns in the hyperbolic plane, and in combinatorial designs. Moreover, Babai has shown that all graphs can be realized as an induced

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

Packing paths in digraphs

✍ Richard C. Brewster; Pavol Hell; Sarah H. Pantel; Romeo Rizzi; Anders Yeo 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB

## Abstract Let ${\cal G}$ be a fixed set of digraphs. Given a digraph __H__, a ${\cal G}$‐packing in __H__ is a collection ${\cal P}$ of vertex disjoint subgraphs of __H__, each isomorphic to a member of ${\cal G}$. A ${\cal G}$‐packing ${\cal P}$ is __maximum__ if the number of vertices belonging

Distance connectivity in graphs and digr

Distance connectivity in graphs and digraphs

✍ Balbuena, M. C.; Carmona, A.; Fiol, M. A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 642 KB

Let G = ( V , A ) be a digraph with diameter D # 1. For a given integer 2 5 t 5 D , the t-distance connectivity K ( t ) of G is the minimum cardinality of an z --+ y separating set over all the pairs of vertices z, y which are a t distance d(z, y) 2 t. The t-distance edge connectivity X ( t ) of G i

Short cycles in digraphs

✍ Tsuyoshi Nishimura 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Caccetta and Haggkvist [l] conjectured that every digraph with n vertices and minimum outdegree k contains a directed cycle of length at most [n/k]. With regard to this conjecture, Chvatal and Szemeredi [2] proved that if G is a digraph with n vertices and if each of these vertices has outdegree at