MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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"

share|cite|improve this answer

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".

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.