##
**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 p_{1}(n) = 2× n^{-3/2}, x > 0, is a lower sharp threshold function and p_{2}(n) = ((3/2+\epsilon_{n}) log n/n)^{ ½}, where \epsilon_{n} = (log log n+ log(3/8)+2x)/(2 log), is an upper sharp threshold function. A probability below p_{1}(n) causes almost all graphs to consist of only isolated edges and vertices, a probability above p_{2}(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