Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903218 | Discrete Mathematics | 2017 | 12 Pages |
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+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).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Han Ren, Chao Yang, Tian-xiao Zhao,