✦ LIBER ✦

The Diameter of Sparse Random Graphs

✍ Scribed by Fan Chung; Linyuan Lu

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 150 KB
Volume: 26
Category: Article
ISSN: 0196-8858
DOI: 10.1006/aama.2001.0720

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the diameter of a random graph G n p for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of random graph G n p is close to log n log np if np → ∞. Moreover if np log n = c > 8, then the diameter of G n p is concentrated on two values. In general, if np log n = c > c 0 , the diameter is concentrated on at most 2 1/c 0 + 4 values. We also proved that the diameter of G n p is almost surely equal to the diameter of its giant component if np > 3 6.

📜 SIMILAR VOLUMES

Bisecting sparse random graphs

✍ Malwina J. Luczak; Colin McDiarmid 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB 👁 1 views

Sparse pseudo-random graphs are Hamilton

Sparse pseudo-random graphs are Hamiltonian

✍ Michael Krivelevich; Benny Sudakov 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB

## Abstract In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a __d__‐regular graph __G__ on __n__ vertices satisfies and __n__ is large enough, then __G__ is Hamiltonian. We also show how our main resu

Independent sets in random sparse graphs

✍ Pedro G. Gazmuri 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 418 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

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

Maximum matchings in sparse random graph

Maximum matchings in sparse random graphs: Karp–Sipser revisited

✍ Jonathan Aronson; Alan Frieze; Boris G. Pittel 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 490 KB 👁 1 views

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on x Foundations of Computing, 1981, pp. 3