✦ LIBER ✦

Partition of a directed bipartite graph into two directed cycles

✍ Scribed by Hong Wang; Charles Little; Kee Teo

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 356 KB
Volume: 160
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00165-s

No coin nor oath required. For personal study only.

✦ Synopsis

Let D = (V1, V2; A) be a directed bipartite graph with II/11 = 11/21 = n ~> 2. Suppose that do(x) + do(y) >~ 3n + 1 for all xe I/1 and ye V2. Then D contains two vertex-disjoint directed cycles of lengths 2nl and 2n2, respectively, for any positive integer partition n = n~ + n2. Moreover, the condition is sharp for even n and nearly sharp for odd n.

📜 SIMILAR VOLUMES

Partition of a bipartite hamiltonian gra

Partition of a bipartite hamiltonian graph into two cycles

✍ Denise Amar 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 480 KB

We prove the following theorem. "I'neorem. If G is a balanced bipartite graph with bipartition (A, B), [A I = IBI = n, such that for any x ~ A, y ~ B, d(x) + d(y) >>-n + 2, then for any (nl, n2), ni >I 2, n -----n I + hE, G contains two independent cycles of lengths 2nl and 2n2.

Partition of a bipartite graph into cycl

Partition of a bipartite graph into cycles

✍ Hong Wang 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 241 KB

Wang, H., Partition of bipartite graph into cycles, Discrete Mathematics 117 (1993) 287-291. El-Zahar (1984) conjectured that if G is a graph on n, + n, + + nk vertices with ni > 3 for 1s i < k and minimum degree 6(G)>rn,/21+rn2/21+ ... +rn,/21, then G contains k vertex-disjoint cycles of lengths n,

A matrix method for location of cycles o

A matrix method for location of cycles of a directed graph

✍ R. L. Norman 📂 Article 📅 1965 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 269 KB 👁 3 views

A comparison of three algorithms for fin

A comparison of three algorithms for finding fundamental cycles in a directed graph

✍ Doris R. Ryan; Stephen Chen 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 543 KB

## Abstract Given a connected directed graph and a spanning tree, we consider the problem of finding the set of fundamental cycles. In particular, for each cotree arc __i__ and tree arc __j__, we need to know whether or not __i__ and __j__ are in the same fundamental cycle, and if so, whether or no

On the cycle polytope of a directed grap

On the cycle polytope of a directed graph

✍ Egon Balas; Maarten Oosten 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

When the cartesian product of two direct

When the cartesian product of two directed cycles is hyperhamiltonian

✍ Joseph A. Gallian; David Witte 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB

We say a digraph G is hyperhamiltonian if there is a spanning closed walk in G which passes through one vertex exactly twice and all others exactly once. We show the Cartesian product Z, x Z, of two directed cycles is hyperhamiltonian if and only if there are positive integers rn and n with ma + nb