  We investigate random processes for generating task-dependency graphs of
order $n$ with $m$ edges and a specified number of initial vertices and
terminal vertices. In order to do so, we consider two random processes for
generating task-dependency graphs that can be combined to accomplish this task.
In the $(x, y)$ edge-removal process, we start with a maximally connected
task-dependency graph and remove edges uniformly at random as long as they do
not cause the number of initial vertices to exceed $x$ or the number of
terminal vertices to exceed $y$. In the $(x, y)$ edge-addition process, we
start with an empty task-dependency graph and add edges uniformly at random as
long as they do not cause the number of initial vertices to be less than $x$ or
the number of terminal vertices to be less than $y$. In the $(x, y)$
edge-addition process, we halt if there are exactly $x$ initial vertices and
$y$ terminal vertices. For both processes, we determine the values of $x$ and
$y$ for which the resulting task-dependency graph is guaranteed to have exactly
$x$ initial vertices and $y$ terminal vertices, and we also find the extremal
values for the number of edges in the resulting task-dependency graphs as a
function of $x$, $y$, and the number of vertices. Furthermore, we
asymptotically bound the expected number of edges in the resulting
task-dependency graphs. Finally, we define a random process using only
edge-addition and edge-removal, and we show that with high probability this
random process generates an $(x, y)$ task-dependency graph of order $n$ with
$m$ edges.
