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