The decycling number of graphs
Sheng Bau, Lowell W. Beineke, Fort Wayne · 2002
Abstract. For a graph G and S ⊂ V (G), if G − S is acyclic, then S is said to be a decycling set of G. The size of a smallest decycling set of G is called the decycling number of G. The purpose of this paper is to provide a review of recent results and open problems on this parameter. Results to be reviewed include recent work on decy-cling numbers of cubes, grids and snakes and bounds on the decycling number of cubic graphs, and expected bounds on the decycling numbers of random regular graphs. A structural description of graphs with a fixed decycling number based on connectivity is also presented. 1. Decycling a Graph The minimum number of edges whose removal eliminates all cycles in a given graph has been known as the cycle rank of the graph, and this parameter has a simple expression: b(G) = ‖G‖−|G|+ω ([14], Chapter 4) where, as in [12], |G | and ‖G ‖ are respectively the number of vertices and the number of edges of G and ω is the number of components of G. The corresponding problem of eliminating all cycles from a graph by means of deletion of vertices goes back at least to the work of Kirchhoff [16] on spanning trees. This problem