Maximum acyclic and fragmented sets in regular graphs |
| |
| Authors: | Penny Haxell Oleg Pikhurko Andrew Thomason |
| |
| Affiliation: | 1. Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario N2L 3G1, Canada;2. Department of Mathematical Sciences Carnegie Mellon University Pittsburgh, Pennsylvania 15213 http://www.math.cmu.edu/～pikhurko/;3. Centre for Mathematical Sciences Cambridge University Cambridge CB3 0WB, United Kingdom |
| |
| Abstract: | We show that a typical d‐regular graph G of order n does not contain an induced forest with around  vertices, when n ? d ? 1, this bound being best possible because of a result of Frieze and ?uczak [6]. We then deduce an affirmative answer to an open question of Edwards and Farr (see [4]) about fragmentability, which concerns large subgraphs with components of bounded size. An alternative, direct answer to the question is also given. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 149–156, 2008 |
| |
| Keywords: | connectivity components decycling number fragmentability random regular graphs |
|
|
