A new formula for the decycling number of regular graphs

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 cycle. A decycling set containing exactly ∇(G) vertices of G is called a ∇-set. For any decycling set S of a k-regular graph G, we show that |S|=β(G)+m(S)k−1, where β(G) is the cycle rank of G, m(S)=c+|E(S)|−1 is the margin number of S, c and |E(S)| are, respectively, the number of components of G−S and the number of edges in G[S]. In particular, for any ∇-set S of a 3-regular graph G, we prove that m(S)=ξ(G), where ξ(G) is the Betti deficiency of G. This implies that the decycling number of a 3-regular graph G is β(G)+ξ(G)2. Hence ∇(G)=⌈β(G)2⌉ for a 3-regular upper-embeddable graph G, which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute Z(G), the cardinality of a maximum nonseparating independent set in a 3-regular graph G, which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph G, we show that for any ∇-set S of G, there exists a spanning tree T of G such that the elements of S are simply the leaves of T with at most two exceptions providing ∇(G)=⌈β(G)3⌉. On the other hand, if G is a loopless graph on n vertices with maximum degree at most 4, then ∇(G)≤n+12,if G is 4-regular,n2,otherwise.The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006).