Induced forests in regular graphs with large girth

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

An induced forest of a graph G is an acyclic induced subgraph of G. The present paper is devoted to the analysis of a simple randomised algorithm that grows an induced forest in a regular graph. The expected size of the forest it outputs provides a lower bound on the maximum number of vertices in an induced forest of G. When the girth is large and the degree is at least 4, our bound coincides with the best bound known to hold asymptotically almost surely for random regular graphs. This results in an alternative proof for the random case.
24 pages

Keywords

Combinatorics, 05C35

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/138384

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0709.3126
 http://arxiv.org/abs/0709.3126

Collections

arXiv