The Library
Maximum acyclic and fragmented sets in regular graphs
Tools
Tools
Tools
Haxell, Penny, Pikhurko, Oleg and Thomason, Andrew (2008) Maximum acyclic and fragmented sets in regular graphs. Journal of Graph Theory, Vol.57 (No.2). pp. 149-156. doi:10.1002/jgt.20271 ISSN 0364-9024.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1002/jgt.20271
Abstract
We show that a typical d-regular graph G of order n does not contain an induced forest with around equation image 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.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Journal or Publication Title: | Journal of Graph Theory | ||||
| Publisher: | John Wiley & Sons Ltd. | ||||
| ISSN: | 0364-9024 | ||||
| Official Date: | February 2008 | ||||
| Dates: |
|
||||
| Volume: | Vol.57 | ||||
| Number: | No.2 | ||||
| Number of Pages: | 8 | ||||
| Page Range: | pp. 149-156 | ||||
| DOI: | 10.1002/jgt.20271 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Funder: | NSERC, NSF | ||||
| Grant number: | DMS-0457512 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
