✦ LIBER ✦

Partition of a bipartite graph into cycles

✍ Scribed by Hong Wang

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 241 KB
Volume: 117
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90345-t

No coin nor oath required. For personal study only.

✦ Synopsis

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,, nz, , n, respectively. He proved this conjecture for k=2. In this note we consider a similar problem in bipartite graphs and prove: If G is a bipartite graph with partites V, and V, where IV,I=IV,I=n,n=n,+n,+... +n, for n,>n,> ..' >n,>2, k>2 and G(G)>n,+n,+ '.. +n,_ 1 +n,/2, then G contains k vertex-disjoint cycles of lengths 2n,, 2nz, ,,, , 2n,, respectively, We demonstrate by producing examples that the above result is best possible when k=2.

📜 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 directed bipartite graph

Partition of a directed bipartite graph into two directed cycles

✍ Hong Wang; Charles Little; Kee Teo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 356 KB

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 condit

Partitioning Complete Bipartite Graphs b

Partitioning Complete Bipartite Graphs by Monochromatic Cycles

✍ P.E. Haxell 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 886 KB

For every positive integer r there exists a constant C r depending only on r such that for every colouring of the edges of the complete bipartite graph K n, n with r colours, there exists a set of at most C r monochromatic cycles whose vertex sets partition the vertex set of K n, n . This answers a

Partitioning random graphs into large cy

Partitioning random graphs into large cycles

✍ A.M. Frieze 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 833 KB

Let r 3 1 be a tied positive integer. We give the limiting distribution for the probability that the vertices of a random graph can be partitioned equitably into I cycles.

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Proof of a conjecture on cycles in a bip

Proof of a conjecture on cycles in a bipartite graph

✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 2 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. W