Has the following kind of (minimum degree $d$) random graph been studied? - MathOverflow

Has the following kind of (minimum degree $d$) random graph been studied?

2011-02-24T22:26:49Z

The following random construction is simple enough that I am guessing it must have been studied. Fix $d \ge 3$, and let $n > d$. For each of the $n$ vertices, pick exactly $d$ other vertices to connect it to, uniformly over all ${n-1 \choose d}$ possible choices, and making this choice independently over all $n$ vertices. Some edges may get put in twice, and that's fine, but we will consider the final graph to not have multiple edges.

Has this model been studied, and if so does it have a name?

Motivation: Erdos-Renyi random graphs $G(n,p)$ must have average vertex degree greater than, before they become connected and have nice expansion properties, etc. But this is because they still have isolated vertices. Here we don't have the problem of isolated vertices. (I think I can show that these graphs are a.a.s. connected.) I am aware of the large literature on random $d$-regular graphs, but I thought this might be an alternative model if one does not care about regularity.

I am especially wondering about spectral properties of these graphs.

Answer by Flo Pfender for Has the following kind of (minimum degree $d$) random graph been studied?

2011-02-25T12:27:44Z

Yes, this model has been studied. For some early results, see

Fenner, T. I.; Frieze, A. M. On the connectivity of random $m$-orientable graphs and digraphs. Combinatorica 2 (1982), no. 4, 347–359.

So there it is called "random $m$-orientable graph"

Answer by Gjergji Zaimi for Has the following kind of (minimum degree $d$) random graph been studied?

2011-02-25T12:47:04Z

The main aspect of the underlying graph of a random $m$-out graph (each vertex is given a random set of $m$ out-edges) that has been studied is the fact that they are a.s. Hamiltonian.

Denoting this graph by $D_m(n)$, it is known that $D_2$ almost surely contains a vertex adjacent to three vertices of degree two, and in the paper "On the existence of Hamiltonian cycles in a class of random graphs" Fenner and Frieze proved that $D_{23}$ is a.s. Hamiltonian. Finally Bohman and Frieze recently proved that $D_3$ is almost surely Hamiltonian in "Hamiltonian cycles in $3$-out".