𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Addendum to “trees in random graphs”

✍ Scribed by P Erdös; Z Palka

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
30 KB
Volume
48
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The aim of this addendum is to explain more precisely the second part of the proof of Theorem 1 from our paper [1]. We need to show that a.e. graph G e~J(n,p) contains a maximal induced tree of order less than (l+e)X (log n)/(log d). The second moment method used in our Lemma shows in fact that

📜 SIMILAR VOLUMES

Trees in random graphs
Trees in random graphs
✍ P. Erdös; Z. Palka 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 183 KB
Random trees and random graphs
Random trees and random graphs
✍ Tomasz Łuczak 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 205 KB 👁 2 views

In the paper we study the asymptotic behavior of the number of trees with n Ž . Ž . vertices and diameter k s k n , where n y k rnª a as n ª ϱ for some constant a-1. We use this result to determine the limit distribution of the diameter of the random graph Ž .

Trees in sparse random graphs
Trees in sparse random graphs
✍ W.Fernandez de la Vega 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 471 KB
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

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