✦ LIBER ✦

Maximal induced trees in sparse random graphs

✍ Scribed by Tomasz łuczak; Zbigniew Palka

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 493 KB
Volume: 72
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90215-4

No coin nor oath required. For personal study only.

✦ Synopsis

A study of the orders of maximal induced trees in a random graph G, with small edge probability p is given. In particular, it is shown that the giant component of almost every G,, where p = c/n and c > 1 is a constant, contains only very small maximal trees (that are of a specific type) and very large maximal trees. The presented results provide an elementary proof of a conjecture from [3] that was confirmed recently in [4] and [5].

Note added in proof

Similar results were proved recently by L. KuEera and V. RodI in large trees in random graphs, Comment. Math. Univ. Carolin. 28 (1987) 7-14.

📜 SIMILAR VOLUMES

Large induced trees in sparse random gra

Large induced trees in sparse random graphs

✍ A.M Frieze; B Jackson 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 621 KB

Trees in sparse random graphs

✍ W.Fernandez de la Vega 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 471 KB

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 large induced trees and long induced

On large induced trees and long induced paths in sparse random graphs

✍ W.C.Stephen Suen 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 697 KB

On-Line Coloring of Sparse Random Graphs

On-Line Coloring of Sparse Random Graphs and Random Trees

✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 164 KB

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random gr

Trees in random graphs

✍ P. Erdös; Z. Palka 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 183 KB