Regular induced subgraphs of a random Graph |
| |
| Authors: | Michael Krivelevich Benny Sudakov Nicholas Wormald |
| |
| Affiliation: | 1. School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel;2. Department of Mathematics, University of California, Los Angeles (UCLA), Los Angeles, California 90095;3. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada |
| |
| Abstract: | An old problem of Erd?s, Fajtlowicz, and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on  vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on  vertices, i.e., in a binomial random graph  . We prove that with high probability a largest induced regular subgraph of  has about  vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 235–250, 2011 |
| |
| Keywords: | regular induced subgraph random graph extremal graph theory random regular graphs |
|
|
