## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  529.05053
Autor:  Erdös, Paul; Palmer, Edgar M.; Robinson, Robert W.
Title:  Local connectivity of a random graph. (In English)
Source:  J. Graph Theory 7, 411-417 (1983).
Review:  The authors investigate the probability that a random graph is locally connected. A graph is called locally connected if for each vertex v of degree \geq 2, the subgraph induced by the vertices adjacent to v is connected. Appropriate probabilities p(n) for an edge of a graph of order n are assumed, and for n ––> oo the limiting distribution of a graph to be locally connected is evaluated. It turns out that p1(n) = 2× n-3/2, x > 0, is a lower sharp threshold function and p2(n) = ((3/2+\epsilonn) log n/n) ½, where \epsilonn = (log log n+ log(3/8)+2x)/(2 log), is an upper sharp threshold function. A probability below p1(n) causes almost all graphs to consist of only isolated edges and vertices, a probability above p2(n) causes almost all graphs to be locally connected.
Reviewer:  W.Schlee. \end
Classif.:  * 05C80 Random graphs
05C40 Connectivity
60C05 Combinatorial probability
Keywords:  local connectivity; induced subgraph; neighbourhood connected; threshold function

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag