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|=[formule Ommited], 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 [formule Ommited]. Hence ∇(G)=⌈[formule Ommited]⌉ 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)=⌈[formule Ommited]⌉. On the other hand, if G is a loopless graph on n vertices with maximum degree at most 4, then ∇(G)≤[formule Ommited], if G is 4-regular, [formule Ommited], otherwise. The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006).