A new formula for the decycling number of regular graphs

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 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 + 1 2 , if G is 4-regular , n 2 , otherwise . The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006).