Premium
On random k ‐out subgraphs of large graphs
Author(s) -
Frieze Alan,
Johansson Tony
Publication year - 2017
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20650
Subject(s) - combinatorics , random graph , mathematics , bounded function , struct , random regular graph , graph , degree (music) , discrete mathematics , hamiltonian path , hamiltonian (control theory) , chordal graph , physics , 1 planar graph , computer science , mathematical analysis , mathematical optimization , acoustics , programming language
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 ) ) wherelim n → ∞ ϕ ( n ) = 0 . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017