𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the order of the largest induced tree in a random graph

✍ Scribed by Zbigniew Palka; Andrzej Ruciński

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
305 KB
Volume
15
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

On the largest tree of given maximum deg
On the largest tree of given maximum degree in a connected graph
✍ Y. Caro; I. Krasikov; Y. Roditty 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB 👁 1 views

## Abstract We prove that every connected graph __G__ contains a tree __T__ of maximum degree at most __k__ that either spans __G__ or has order at least __k__δ(__G__) + 1, where δ(__G__) is the minimum degree of __G.__ This generalizes and unifies earlier results of Bermond [1] and Win [7]. We als

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

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 largest tree in certain models of ra
The largest tree in certain models of random forests
✍ Ljuben Mutafchiev 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB 👁 2 views

We consider four families of forests on n vertices: labeled and unlabeled forests containing rooted and unrooted trees, respectively. A forest is chosen uniformly from one of the given four families. The limiting distribution of the size of its largest tree is then studied as n ª ϱ. Convergences to