✦ LIBER ✦

Partitioning random graphs into large cycles

✍ Scribed by A.M. Frieze

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 833 KB
Volume: 70
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90089-1

No coin nor oath required. For personal study only.

✦ Synopsis

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.

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

Cycles in random graphs

✍ Tomasz Łuczak 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 348 KB

tuczak, T., Cycles in random graphs, Discrete Mathematics 98 (1991) 231-236. Let G(n, p) be a graph on n vertices in which each possible edge is presented independently with probability p = p(n) and u'(n, p) denote the number of vertices of degree 1 in G(n, p). It is shown that if E > 0 and rip(n)))

On large matchings and cycles in sparse

On large matchings and cycles in sparse random graphs

✍ A.M Frieze 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 666 KB

Let k be a fixed positive integer. A graph H has property Mk if it contains [½k] edge disjoint hamilton cycles plus a further edge disjoint matching which leaves at most one vertex isolated, if k is odd. Let p = c/n, where c is a large enough constant. We show that G,,p a.s. contains a vertex induce

General Partitioning on Random Graphs

✍ C.R. Subramanian; C.E. Veni Madhavan 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 158 KB

Consider the general partitioning (GP) problem defined as follows: Partition the vertices of a graph into k parts W 1 W k satisfying a polynomial time verifiable property. In particular, consider properties (introduced by T. Feder, P. Hell, S. Klein, and R. Motwani, in "Proceedings of the Annual ACM

Large cycles in graphs

✍ J.A. Bondy 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 485 KB

Abstrtct. The paper i~ concerned with the existence of cycles of specified length in finite undirected graphs and with the question of how this depends on the numbers of vertit.¢s and edges ~ ulje graph, In particular, a conjecture ofP. Erdiss that every graph of order n and size at least ](n 2-5n ¢

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.