✦ LIBER ✦

The largest component in a random subgraph of the n-cycle

✍ Scribed by Gyula O.H. Katona; Louis V. Quintas

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 214 KB
Volume: 121
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90543-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A generating function approach to random

A generating function approach to random subgraphs of the n-cycle

✍ Xavier Gourdon; Helmut Prodinger 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 226 KB

Given a cycle with n nodes a random subgraph is created by 'accepting' edges with probability p and 'rejecting' them with probability q = 1 -p. The parameter of interest is the order of the largest component. There are some partial answers to this question in the literature. Using an appropriate enc

On the Largest Component of the Random G

On the Largest Component of the Random Graph at a Nearcritical Stage

✍ Boris Pittel 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 225 KB

The random graphs G(n, Pr(edge)= p), G(n, \*edges=M) at the critical range p=(1+\*n &1Â3 )Ân and M=(nÂ2)(1+\*n &1Â3 ) are studied. The limiting distribution of the largest component size is determined.

The size of the largest hole in a random

The size of the largest hole in a random graph

✍ Tomasz Łuczak 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 775 KB

Let H(n, p) denote the size of the largest induced cycle in a random graph C(n, p). It is shown that if the expected average degree of G(n, p) is a constant larger than 1, then H(n, p) is of the order n with probability 1 -o(l). Moreover, for C(n, p) with large average degree, H(n, p) is determined

Asymptotic normality of subcubes in rand

Asymptotic normality of subcubes in random subgraphs of the n-cube

✍ Urzula Konieczna 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 275 KB

We consider two types of random subgraphs of the n-cube. For these models we study the asymptotic behaviour of the number of d-cubes when d = 1,2,

On the asymptotic distributions of subgr

On the asymptotic distributions of subgraph counts in a random tournament

✍ Pontus Andersson 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB 👁 2 views

A random tournament T is obtained by independently orienting the edges of n 1 the complete graph on n vertices, with probability for each direction. We study the 2 asymptotic distribution, as n tends to infinity, of a suitable normalization of the number of subgraphs of T that are isomorphic to a gi

The largest induced tree in a sparse ran

The largest induced tree in a sparse random graph

✍ W. Fernandez de la Vega 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 2 views

The author proved that, for c > 1, the random graph G(n, p ) on n vertices with edge probability p = c / n contains almost always an induced tree on at least q n ( 1 -o( 1)) vertices, where L Y ~ is the positive root of the equation CLY = log( 1 + c'a). It is shown here that if c is sufficiently lar