Name
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 $n$ **image** vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on $n$ **image** vertices, i.e., in a binomial random graph $G(n,1/2)$ **image** . We prove that with high probability a largest induced regular subgraph of $G(n,1/2)$ **image** has about $n^{2/3}$ **image** vertices. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 235–250, 2011 © 2011 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1002/rsa.20324 | Random Struct. Algorithms |
Keywords | Field | DocType |
random graph,binomial random graph,high probability,wiley periodicals,largest induced regular subgraph,typical graph,inc. random struct,regular induced subgraphs,old problem,extremal graph theory | Random regular graph,Discrete mathematics,Combinatorics,Graph factorization,Induced subgraph isomorphism problem,Distance-hereditary graph,Regular graph,Factor-critical graph,Mathematics,Degeneracy (graph theory),Path graph | Journal |
Volume | Issue | ISSN |
38 | 3 | 1042-9832 |
Citations | PageRank | References |
2 | 0.41 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| michael krivelevich | 1 | 1688 | 179.90 |
| Benny Sudakov | 2 | 1391 | 159.71 |
| Nicholas C. Wormald | 3 | 1506 | 230.43 |