On the Probability of Connectedness of a Random Graph $\mathcal{G}_m (t)$
V. E. Stepanov · Theory of Probability and Its Applications · 1970
Previous article Next article On the Probability of Connectedness of a Random Graph $\mathcal{G}_m (t)$V. E. StepanovV. E. Stepanovhttps://doi.org/10.1137/1115004PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] V. E. Stepanov, Combinatorial algebra and random graphs, Theory Prob. Applications, 14 (1969), 373–399 10.1137/1114052 0239.05124 LinkGoogle Scholar[2] P. Erdo˝s and , A. Rényi, On random graphs. I, Publ. Math. Debrecen, 6 (1959), 290–297 MR0120167 0092.15705 Google Scholar[3] P. Erdo˝s and , A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), 17–61 MR0125031 Google Scholar[4] V. E. Stepanov, Limit distributions of certain characteristics of random mappings, Theory Prob. Applications, 14 (1969), 612–626 10.1137/1114078 LinkGoogle Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails ℓ $\ell $‐Connectivity and ℓ $\ell $‐edge‐connectivity of random graphsJournal of Graph Theory, Vol. 101, No. 1 | 18 February 2022 Cross Ref A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graphRandom Structures & Algorithms, Vol. 59, No. 4 | 5 April 2021 Cross Ref Vanishing of cohomology groups of random simplicial complexesRandom Structures & Algorithms, Vol. 56, No. 2 | 23 April 2019 Cross Ref Note on directed proper connection number of a random graphApplied Mathematics and Computation, Vol. 361 | 1 Nov 2019 Cross Ref Mixed connectivity properties of random graphs and some special graphsJournal of Combinatorial Optimization, Vol. 14 | 14 May 2019 Cross Ref Swendsen‐Wang algorithm on the mean‐field Potts modelRandom Structures & Algorithms, Vol. 54, No. 1 | 6 March 2018 Cross Ref Mixed Connectivity of Random GraphsCombinatorial Optimization and Applications | 17 November 2017 Cross Ref Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphsRandom Structures & Algorithms, Vol. 49, No. 1 | 18 November 2015 Cross Ref Inside the critical window for cohomology of random k -complexesRandom Structures & Algorithms, Vol. 48, No. 1 | 29 January 2015 Cross Ref Giant components in random graphsRecent Trends in Combinatorics | 13 April 2016 Cross Ref Local limit theorems via Landau–Kolmogorov inequalitiesBernoulli, Vol. 21, No. 2 | 1 May 2015 Cross Ref Local Limit Theorems for the Giant Component of Random HypergraphsCombinatorics, Probability and Computing, Vol. 23, No. 3 | 13 February 2014 Cross Ref The Asymptotic Number of Connected d -Uniform HypergraphsCombinatorics, Probability and Computing, Vol. 23, No. 3 | 13 February 2014 Cross Ref Cutting Edges at Random in Large Recursive TreesStochastic Analysis and Applications 2014 | 14 December 2014 Cross Ref On the non-Gaussian fluctuations of the giant cluster for percolation on random recursive treesElectronic Journal of Probability, Vol. 19, No. none | 1 Jan 2014 Cross Ref On the normality of giant componentsRandom Structures & Algorithms, Vol. 43, No. 4 | 25 October 2012 Cross Ref On z -analogue of Stepanov–Lomonosov–Polesskii inequalityJournal of Combinatorial Theory, Series B, Vol. 103, No. 6 | 1 Nov 2013 Cross Ref The order of the giant component of random hypergraphsRandom Structures & Algorithms, Vol. 36, No. 2 | 24 August 2009 Cross Ref Local Limit Theorems for the Giant Component of Random HypergraphsApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 1 Jan 2007 Cross Ref Stochastic processes in random graphsThe Annals of Probability, Vol. 33, No. 1 | 1 Jan 2005 Cross Ref On the Largest Component of the Random Graph at a Nearcritical StageJournal of Combinatorial Theory, Series B, Vol. 82, No. 2 | 1 Jul 2001 Cross Ref A phase transition phenomenon in a random directed acyclic graphRandom Structures and Algorithms, Vol. 18, No. 2 | 1 January 2001 Cross Ref A phase transition phenomenon in a random directed acyclic graphRandom Structures and Algorithms, Vol. 18, No. 2 | 1 January 2001 Cross Ref Phase transition phenomena in random discrete structuresDiscrete Mathematics, Vol. 136, No. 1-3 | 1 Dec 1994 Cross Ref The structure of a random graph at the point of the phase transitionTransactions of the American Mathematical Society, Vol. 341, No. 2 | 1 January 1994 Cross Ref Multicyclic components in a random graph processRandom Structures & Algorithms, Vol. 4, No. 1 | 11 October 2006 Cross Ref Components of Random ForestsCombinatorics, Probability and Computing, Vol. 1, No. 1 | 12 September 2008 Cross Ref Random subgraphs of the n-cycle and the n-wheelDiscrete Mathematics, Vol. 93, No. 1 | 1 Nov 1991 Cross Ref On tree census and the giant component in sparse random graphsRandom Structures & Algorithms, Vol. 1, No. 3 | 11 October 2006 Cross Ref A generalization of an inequality of StepanovJournal of Combinatorial Theory, Series B, Vol. 48, No. 2 | 1 Apr 1990 Cross Ref The asymptotic number of labeled connected graphs with a given number of vertices and edgesRandom Structures and Algorithms, Vol. 1, No. 2 | 1 Jan 1990 Cross Ref On the Behavior of a Random Graph Near a Critical PointTheory of Probability & Its Applications, Vol. 31, No. 3 | 28 July 2006AbstractPDF (1004 KB)Random Graphs of Small OrderRandom Graphs '83, Based on lectures presented at the 1st Poznań Seminar on Random Graphs | 1 Jan 1985 Cross Ref A review of random graphsJournal of Graph Theory, Vol. 6, No. 4 | 1 Jan 1982 Cross Ref Criticality and the Emergence of StructureEvolution of Order and Chaos | 1 Jan 1982 Cross Ref Threshold limit theorems for some epidemic processesAdvances in Applied Probability, Vol. 12, No. 02 | 1 July 2016 Cross Ref Threshold limit theorems for some epidemic processesAdvances in Applied Probability, Vol. 12, No. 2 | 1 July 2016 Cross Ref The expected linearity of a simple equivalence algorithmTheoretical Computer Science, Vol. 6, No. 3 | 1 Jan 1978 Cross Ref On Extreme Metric Characteristics of a Random Graph. II. Limit DistributionsTheory of Probability & Its Applications, Vol. 20, No. 1 | 17 July 2006AbstractPDF (1185 KB)On Extreme Metric Parameters of a Random Graph. I. Asymptotic EstimatesTheory of Probability & Its Applications, Vol. 19, No. 4 | 28 July 2006AbstractPDF (1056 KB)Asymptotic estimates of the degree of connectivity of a random graphCybernetics, Vol. 9, No. 3 | 1 Jan 1975 Cross Ref The Strength of Connectivity of a Random GraphTheory of Probability & Its Applications, Vol. 18, No. 2 | 17 July 2006AbstractPDF (730 KB)On the Asymptotic Behavior of Degrees of Vertices in a Random GraphTheory of Probability & Its Applications, Vol. 18, No. 1 | 28 July 2006AbstractPDF (657 KB)Structure of the Random Graphs $\mathcal{G}_m (x|h)$Theory of Probability & Its Applications, Vol. 17, No. 2 | 17 July 2006AbstractPDF (1268 KB)Phase Transitions in Random GraphsTheory of Probability & Its Applications, Vol. 15, No. 2 | 17 July 2006AbstractPDF (1520 KB) Volume 15, Issue 1| 1970Theory of Probability & Its Applications1-162 History Submitted:17 March 1969Published online:17 February 2012 InformationCopyright © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/1115004Article page range:pp. 55-67ISSN (print):0040-585XISSN (online):1095-7219Publisher:Society for Industrial and Applied Mathematics