๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Induced trees in sparse random graphs

โœ Scribed by W. Fernandez de la Vega

Publisher
Springer Japan
Year
1986
Tongue
English
Weight
278 KB
Volume
2
Category
Article
ISSN
0911-0119

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

Trees in sparse random graphs
Trees in sparse random graphs
โœ W.Fernandez de la Vega ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 471 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