✦ LIBER ✦

Partition of a bipartite hamiltonian graph into two cycles

✍ Scribed by Denise Amar

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 480 KB
Volume: 58
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90181-0

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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,

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

Alternating hamiltonian cycles in two co

Alternating hamiltonian cycles in two colored complete bipartite graphs

✍ A. G. Chetwynd; A. J. W. Hilton 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 2 views

## Abstract We give necessary and sufficient conditions for the existence of an alternating Hamiltonian cycle in a complete bipartite graph whose edge set is colored with two colors.

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

Packing two forests into a bipartite gra

Packing two forests into a bipartite graph

✍ Wang, Hong 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 292 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 /XI = 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 note, w

Partitioning a graph into two isomorphic

Partitioning a graph into two isomorphic pieces

✍ Anthony Bonato; Richard Nowakowski 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

## Abstract A simple graph __G__ has the neighbour‐closed‐co‐neighbour property, or ncc property, if for all vertices __x__ of __G__, the subgraph induced by the set of neighbours of __x__ is isomorphic to the subgraph induced by the set of non‐neighbours of __x__. We present characterizations of g