Looking for information about a random graph model

Question

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$

Answer 1

This generative model has some interesting properties. It has a fixed average degree with each node having degree at least one. It is also my intuition that it minimizes or comes very close to minimizing clustering for a fixed number of edges. I'm not familiar with any models which behave as the one you are describing. Good for you, it's hard to come up with new models nowadays =).

Answer 2

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.

One place that you can read about this models is Alan Frieze and Michal Karoński's new book on Random Graphs. An early copy of this book is at http://www.math.cmu.edu/~af1p/Book.html