Has the following kind of (minimum degree \$d\$) random graph been studied? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T13:58:14Z http://mathoverflow.net/feeds/question/56569 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/56569/has-the-following-kind-of-minimum-degree-d-random-graph-been-studied Has the following kind of (minimum degree \$d\$) random graph been studied? Matthew Kahle 2011-02-24T22:26:49Z 2011-02-25T12:59:46Z <p>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.</p> <blockquote> <p>Has this model been studied, and if so does it have a name?</p> </blockquote> <p>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.</p> <p>I am especially wondering about spectral properties of these graphs.</p> http://mathoverflow.net/questions/56569/has-the-following-kind-of-minimum-degree-d-random-graph-been-studied/56626#56626 Answer by Flo Pfender for Has the following kind of (minimum degree \$d\$) random graph been studied? Flo Pfender 2011-02-25T12:27:44Z 2011-02-25T12:27:44Z <p>Yes, this model has been studied. For some early results, see</p> <p>Fenner, T. I.; Frieze, A. M. On the connectivity of random \$m\$-orientable graphs and digraphs. Combinatorica 2 (1982), no. 4, 347–359.</p> <p>So there it is called "random \$m\$-orientable graph"</p> http://mathoverflow.net/questions/56569/has-the-following-kind-of-minimum-degree-d-random-graph-been-studied/56628#56628 Answer by Gjergji Zaimi for Has the following kind of (minimum degree \$d\$) random graph been studied? Gjergji Zaimi 2011-02-25T12:47:04Z 2011-02-25T12:59:46Z <p>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.</p> <p>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 <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V00-46D1P4C-3B&amp;_user=1010281&amp;_coverDate=12%2F31%2F1983&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_rerunOrigin=scholar.google&amp;_acct=C000050264&amp;_version=1&amp;_urlVersion=0&amp;_userid=1010281&amp;md5=09e6546719ef9ff884b3ea6d5495466f&amp;searchtype=a" rel="nofollow">"On the existence of Hamiltonian cycles in a class of random graphs"</a> 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 <a href="http://arxiv.org/abs/0904.0431?context=math" rel="nofollow">"Hamiltonian cycles in \$3\$-out"</a>.</p>