On the Strongly Connected Components of Random Directed Graphs with Given Degree Sequences

random graphs;directed graphs;strongly connected components;percolation

Graf, Alessandra

University of Waterloo

关键词: random graphs;    directed graphs;    strongly connected components;    percolation;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/10681/1/Graf_Alessandra.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

A strongly connected component of a directed graph G is a maximal subgraph H of G such that for each pair of vertices u and v in H, there is a directed path from u to v and a directed path from v to u in H. A strongly connected component is said to be giant if it has linear size.We determine the threshold at which a random directed graph with a well-behaved degree sequence asymptotically almost surely contains a giant strongly connected component. This is a new proof of a result by Cooper and Frieze in 2004. In addition, we predict the site percolation threshold for the presence of a giant strongly connected component in a graph with a well-behaved degree sequence.