On random k‐out subgraphs of large graphs1. Issue 2 (30th March 2016) - Frieze, Alan; Johansson, Tony
Abstract: We consider random subgraphs of a fixed graph G = ( V, E ) with large minimum degree. We fix a positive integer k and let G k be the random subgraph where each v ∈ V independently chooses k random neighbors, making kn edges in all. When the minimum degree δ ( G ) ≥ ( 1 2 + ε ) n,   n = | V | then G k is k ‐connected w.h.p. for k = O ( 1 ) ; Hamiltonian for k sufficiently large. When δ ( G ) ≥ m, then G k 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 lim n → ∞ ϕ ( n ) = 0 . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017