✦ LIBER ✦

Partition of a graph into cycles and degenerated cycles

✍ Scribed by Hikoe Enomoto; Hao Li

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 177 KB
Volume: 276
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(03)00300-5

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph of order n and k any positive integer with k 6 n. It has been shown by Brandt et al. that if |G| = n ¿ 4k and if the degree sum of any pair of nonadjacent vertices is at least n, then G can be partitioned into k cycles. We prove that if the degree sum of any pair of nonadjacent vertices is at least n -k + 1, then G can be partitioned into k subgraphs Hi, 1 6 i 6 k, where Hi is a cycle or K1 or K2, except G = C5 and k = 2.

📜 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 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 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.

Cycle-cocycle partitions and faithful cy

Cycle-cocycle partitions and faithful cycle covers for locally finite graphs

✍ Henning Bruhn; Reinhard Diestel; Maya Stein 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract By a result of Gallai, every finite graph __G__ has a vertex partition into two parts each inducing an element of its cycle space. This fails for infinite graphs if, as usual, the cycle space is defined as the span of the edge sets of finite cycles in __G__. However, we show that, for t

Covering a graph with cycles

✍ Hong Wang 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 444 KB

## Abstract Let __k__ and __n__ be two integers such that __k__ ≥ 0 and __n__ ≥ 3(__k__ + 1). Let __G__ be a graph of order __n__ with minimum degree at least ⌈(__n__ + __k__)/2⌉. Then __G__ contains __k__ + 1 independent cycles covering all the vertices of __G__ such that __k__ of them are triangl