[PDF][PDF] On the connectivity of random m-orientable graphs and digraphs
TI Fenner, AM Frieze - Combinatorica, 1982 - math.cmu.edu
This paper is concerned with the connectedness of certain random graphs and digraphs.
The most common approach to studying random graphs is either to consi-der a graph GmN
with n vertices and N edges chosen at random (see Erdo's and Rényi [I],[2],[3]), or to fix p, O<
p< 1, and include each possible edge independently with probability p. However, in his
paper on the expected value of a random assignment problem, Walkup [6] uses results on a
random bipartite graph that is generated in the following manner: for each vertex v, generate …
The most common approach to studying random graphs is either to consi-der a graph GmN
with n vertices and N edges chosen at random (see Erdo's and Rényi [I],[2],[3]), or to fix p, O<
p< 1, and include each possible edge independently with probability p. However, in his
paper on the expected value of a random assignment problem, Walkup [6] uses results on a
random bipartite graph that is generated in the following manner: for each vertex v, generate …