Premium
Local connectivity of a random graph
Author(s) -
Erdös P.,
Palmer E. M.,
Robinson R. W.
Publication year - 1983
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190070405
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , random graph , random regular graph , binary logarithm , path graph , connectivity , limiting , discrete mathematics , wheel graph , graph factorization , vertex connectivity , graph power , line graph , 1 planar graph , mechanical engineering , engineering
Abstract A graph is locally connected if for each vertex ν of degree ≧2 , the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order n is p = ((3/2 + ϵ n ) log n/n) 1/2 where ϵ n = (log log n + log(3/8) + 2x)/(2 log n ), then the limiting probability that a random graph is locally connected is exp(‐exp(‐x)).