On random k‐out subgraphs of large graphs |
| |
| Authors: | Alan Frieze Tony Johansson |
| |
| Affiliation: | Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania |
| |
| Abstract: | We consider random subgraphs of a fixed graph  with large minimum degree. We fix a positive integer k and let Gk be the random subgraph where each  independently chooses k random neighbors, making kn edges in all. When the minimum degree  then Gk is k‐connected w.h.p. for  ; Hamiltonian for k sufficiently large. When  , then Gk has a cycle of length  for  . By w.h.p. we mean that the probability of non‐occurrence can be bounded by a function  (or  ) where  . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017 |
| |
| Keywords: | random subgraph Hamilton cycle k‐out |
|
|
with large minimum degree. We fix a positive integer k and let Gk be the random subgraph where each 
independently chooses k random neighbors, making kn edges in all. When the minimum degree 
then Gk is k‐connected w.h.p. for 
; Hamiltonian for k sufficiently large. When 
, then Gk has a cycle of length 
for 
. By w.h.p. we mean that the probability of non‐occurrence can be bounded by a function 
(or 
) where 
. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017