科研之友
微信
新浪微博
Facebook
分享链接
摘要
The decycling number del(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 del(G) vertices of G is called a del-set. For any decycling set S of a k-regular graph G, we show that vertical bar S vertical bar = beta(G)+m(S)/K-1, where beta(G) is the cycle rank of G, m(S) = c + vertical bar E(S)vertical bar - 1 is the margin number of S, c and vertical bar E(S)vertical bar are, respectively, the number of components of G- S and the number of edges in G[S]. In particular, for any del-set S of a 3-regular graph G, we prove that m(S) = xi(G), where xi(G) is the Betti deficiency of G. This implies that the decycling number of a 3-regular graph G is beta(G)+xi(G)/2. Hence del(G) = inverted right perpendicular beta(G)/2inverted left perpendicular 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 del-setS 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 del(G) = inverted right perpendicular beta(G)/3inverted left perpendicular. On the other hand, if G is a loopless graph on n vertices with maximum degree at most 4, then del(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). Published by Elsevier B.V.
