On random k‐out subgraphs of large graphs1. Issue 2 (30th March 2016)

• Record Type: Journal Article
• Authors: Frieze, Alan; Johansson, Tony
• Is Part Of: Random structures & algorithms. Volume 50:Issue 2(2017)
• Page Start: 143
• Page End: 157
• Publication Date: 2016-03-30
• Subjects: random subgraph -- Hamilton cycle -- k‐out; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20650
• Languages: English
• ISSNs: 1042-9832

Abstract

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