## Abstract

The decycling number Φ(G) of a graph G is the smallest number of vertices which can be removed from G so that the resultant graph contains no cycles. In this paper, we study the decycling numbers of random regular graphs. For a random cubic graph G of order n, we prove that Φ(G) = ⌈ n/4 + 1/2 ⌉ holds asymptotically almost surely. This is the result of executing a greedy algorithm for decycling G making use of a randomly chosen Hamilton cycle. For a general random d-regular graph G of order n, where d ≥ 4, we prove that Φ(G)/n can be bounded below and above asymptotically almost surely by certain constants b(d) and B(d), depending solely on d, which are determined by solving, respectively, an algebraic equation and a system of differential equations.

Original language | English |
---|---|

Pages (from-to) | 397-413 |

Number of pages | 17 |

Journal | Random Structures and Algorithms |

Volume | 21 |

Issue number | 3-4 |

Publication status | Published - Oct 2002 |

Externally published | Yes |