Local connectivity of a random graph | Zendy

Erdös P. | Zendy; Palmer E. M. | Zendy; Robinson R. W. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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)).

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research