𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Trees in sparse random graphs

✍ Scribed by W.Fernandez de la Vega

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
471 KB
Volume
45
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Maximal induced trees in sparse random g
Maximal induced trees in sparse random graphs
✍ Tomasz Ε‚uczak; Zbigniew Palka πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 493 KB

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 lar

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-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
Trees in random graphs
✍ P. ErdΓΆs; Z. Palka πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 183 KB