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