Volume 3
Winter 2008
Number 1

A Note on Thresholds and Connectivity

in Random Directed Graphs

Alasdair J. Graham and David Pike

Abstract: Thresholds and phase transitions have been well studied for several properties of random undirected graphs. In this article we adapt a result of Pal\'asti to the context of directed graphs, thereby allowing thresholds for the uniform random directed graph model $\mathbb{D}(n,M)$ to be used in determining thresholds for the binomial random directed graph model $\mathbb{D}(n,p)$ . We then determine the threshold for strong connectivity in $\mathbb{D}(n,p)$ .