Name
Abstract | ||
|---|---|---|
We show that a typical d-regular graph G of ordern does not contain an induced forest with around2Ind/d vertices, when n d 1, this bound being best possible because of aresult of Frieze and Luczak [6]. We then deduce an affirmativeanswer to an open question of Edwards and Farr (see [4]) aboutfragmentability, which concerns large subgraphs with components ofbounded size. An alternative, direct answer to the question is alsogiven. © 2007 Wiley Periodicals, Inc. J Graph Theory 57:149156, 2008 |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1002/jgt.v57:2 | Journal of Graph Theory |
Keywords | Field | DocType |
regular graph | Graph theory,Random regular graph,Discrete mathematics,Strongly regular graph,Combinatorics,Vertex (geometry),Regular graph,Distance-regular graph,Mathematics,Frieze,Bounded function | Journal |
Volume | Issue | ISSN |
57 | 2 | 0364-9024 |
Citations | PageRank | References |
6 | 0.54 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Penny E. Haxell | 1 | 130 | 16.64 |
| Oleg Pikhurko | 2 | 318 | 47.03 |
| Andrew Thomason | 3 | 244 | 30.16 |