The decycling number of cubic graphs

Abstract

For a graph G, a subset S ⊆ V(G), is said to be a decycling set of G if if G \S is acyclic. The cardinality of smallest decycling set of G is called the decycling number of G and it is denoted by φ(G). Bau and Beineke posed the following problems: Which cubic graphs G with |G |= 2n satisfy φ(G) = [n+1/2]? In this paper, we give an answer to this problem. © Springer-Verlag Berlin Heidelberg 2005.