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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page