A new formula for the decycling number of regular graphs |
| |
Authors: | Han Ren Chao Yang Tian-xiao Zhao |
| |
Affiliation: | 1. Department of Mathematics, East China Normal University, Shanghai, 200241, PR China;2. Shanghai Key Laboratory of Pure Mathematics and Mathematical Practice, Shanghai, 200241, PR China;3. Department of Mathematical Science, Tsinghua University, Beijing, 100084, PR China |
| |
Abstract: | The decycling number of a graph is the smallest number of vertices which can be removed from so that the resultant graph contains no cycle. A decycling set containing exactly vertices of is called a -set. For any decycling set of a -regular graph , we show that , where is the cycle rank of , is the margin number of , and are, respectively, the number of components of and the number of edges in . In particular, for any -set of a 3-regular graph , we prove that , where is the Betti deficiency of . This implies that the decycling number of a 3-regular graph is . Hence for a 3-regular upper-embeddable graph , 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 , the cardinality of a maximum nonseparating independent set in a -regular graph , which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph , we show that for any -set of , there exists a spanning tree of such that the elements of are simply the leaves of with at most two exceptions providing . On the other hand, if is a loopless graph on vertices with maximum degree at most , then The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006). |
| |
Keywords: | Decycling number Margin number Cycle rank Betti deficiency Regular graphs |
本文献已被 ScienceDirect 等数据库收录! |
|