The asymptotic behaviour of Fiedler's algebraic connectivity for random graphs (Q1182983): Difference between revisions

In his earlier papers the author dealt with relations between matrices and graphs. Especially, he studied spectra of random graphs [Algebraic methods in graph theory, Vol. I, Conf. Szeged 1978, Colloq. Math. Soc. Janos Bolyai 25, 313-316 (1981; Zbl 0475.05060)]. The algebraic connectivity of a graph \(G\) was introduced by \textit{M. Fiedler} [Czechosl. Math. J. 23(98), 298-305 (1973; Zbl 0265.05119)] as the second smallest eigenvalue of the Laplacian of \(G\). In the paper under review it is shown that if \(G(n)\) is a 2-block random graph with the expectation \(p_{12}\leq p_{11},p_{22}\) then the algebraic connectivity of \(G(n)\) is \(p_{12}n+o(n^{{1\over 2}+\varepsilon})\) in probability.