##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 674.05056

**Autor: ** Erdös, Paul; Kennedy, J.W.

**Title: ** k-connectivity in random graphs. (In English)

**Source: ** Eur. J. Comb. 8, 281-286 (1987).

**Review: ** Motivated by applications of evolving random graphs as models for phase transitions in physical systems, problems were posed [the second author, k-connectivity and cycles in random graphs with applications, Notes from N. Y. Graph Theory Day I, 3-5 (1980)] concerning threshold functions for the appearance of giant k-connected subgraphs in random graphs, random f- graphs (i.e. random graphs with maximum vertex degree f), and random lattice-graphs (i.e. random graphs restricted to be embeddable in some lattice-graph).

We present here a solution to the problem for the first two classes of random graphs and for all k = 1,2... . The problem concerning random lattice-graphs remains open.

**Classif.: ** * 05C80 Random graphs

05C40 Connectivity

**Keywords: ** evolving random graphs; phase transitions; physical systems; threshold functions

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag