\(k\)-connectivity in random graphs (Q1121288)

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.