# Looking for information about a random graph model

I have the following random graph model, and I am looking for its name and/or any work done concerning it.

Given $n$ nodes, $\{v_1,...,v_n\}$, and $n$ timesteps, proceed as follows: On the $k$th timestep, choose a node, $v_j$ uniformly at random from $\{v_1,...,v_{k-1}, v_{k+1},...,v_n\}$ and add the undirected edge $(v_k, v_j)$ to the graph. Note that this edge may have been added at an earlier timestep, in which case skip adding an edge and proceed to the next timestep.

As an example, for $n=3$:

1) Add edge $(v_1, v_2)$ to the graph.

2) Add edge $(v_2, v_1)$ to the graph. This edge already exists, so do nothing instead.

3) Add edge $(v_3, v_1)$ to the graph.

4) The final graph has two edges, one between $v_1$ and $v_2$ and one between $v_1$ and $v_3$

• Indeed, this is not clear to me. Do we have timesteps? Do we add an edge for each node, or just one edge for the whole graph? Why would 2 edges be a complete graph when $n=3$? – Archaick Apr 22 '15 at 0:07
• Timesteps is probably a more clear way to describe it. I will change the post. – Davis Yoshida Apr 22 '15 at 0:16
• This is much clearer now, thank you. – Archaick Apr 22 '15 at 0:21

That random graph is denoted by $\mathbb{G}_{1-out}$. A common generalization is $\mathbb{G}_{k-out}$, where in step $j$, we choose $k$ vertices out of $V\setminus\{v_j\}$ and add the $k$ edges $\{v_j, \cdot\}$. Then at the end, delete multiple edges.