10.1184/R1/6478775.v1 Alan Frieze Alan Frieze Tony Johansson Tony Johansson On random k-out sub-graphs of large graphs Carnegie Mellon University 2015 Mathematical Sciences 2015-07-11 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/On_random_k-out_sub-graphs_of_large_graphs/6478775 <p>We consider random sub-graphs of a fixed graph G=(V,E) with large minimum degree. We fix a positive integer k and let Gk be the random sub-graph where each v∈V independently chooses k random neighbors, making kn edges in all. When the minimum degree δ(G)≥(12+ϵ)n,n=|V| then Gk is k-connected w.h.p. for k=O(1); Hamiltonian for ksufficiently large. When δ(G)≥m, then Gk has a cycle of length (1−ϵ)m for k≥kϵ. By w.h.p. we mean that the probability of non-occurrence can be bounded by a function ϕ(n) (or ϕ(m)) where limn→∞ϕ(n)=0.</p>