zbMATH — the first resource for mathematics

New formulae for the decycling number of graphs. (English) Zbl 1401.05074
Summary: A set \(S\) of vertices of a graph \(G\) is called a decycling set if \(G-S\) is acyclic. The minimum order of a decycling set is called the decycling number of \(G\), and denoted by \(\nabla(G)\). Our results include: (a) For any graph \(G\), \[ \nabla(G)=n-\max_{T}\{\alpha(G-E(T))\}, \] where \(T\) is taken over all the spanning trees of \(G\) and \(\alpha(G - E(T))\) is the independence number of the co-tree \(G - E(T)\). This formula implies that computing the decycling number of a graph \(G\) is equivalent to finding a spanning tree in \(G\) such that its co-tree has the largest independence number. Applying the formula, the lower bounds for the decycling number of some (dense) graphs may be obtained. (b) For any decycling set \(S\) of a \(k\)-regular graph \(G\), \[ |S|=\frac{1}{k-1}(\beta(G)+m(S)), \] where \(\beta(G) = |E(G)|-|V (G)|+1\) and \(m(S) = c+|E(S)|-1\), \(c\) and \(|E(S)|\) are, respectively, the number of components of \(G - S\) and the number of edges in \(G[S]\). Hence \(S\) is a \(\nabla\)-set if and only if \(m(S)\) is minimum, where \(\nabla\)-set denotes a decycling set containing exactly \(\nabla(G)\) vertices of \(G\). This provides a new way to locate \(\nabla(G)\) for \(k\)-regular graphs \(G\). (c) 4-regular graphs \(G\) with the decycling number \(\nabla(G)\left\lceil \frac{\beta(G)}{3}\right\rceil\) are determined.
05C07 Vertex degrees
05C38 Paths and cycles
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C42 Density (toughness, etc.)
Full Text: DOI
[1] M.O. Albertson and D.M. Berman, The acyclic chromatic number , Congr. Numer. 17 (1976) 51-69. · Zbl 0344.05116
[2] S. Bau and L.W. Beineke, The decycling number of graphs, Australas. J. Combin. 25 (2002) 285-298. · Zbl 0994.05079
[3] L.W. Beineke and R.C. Vandell, Decycling graphs, J. Graph Theory 25 (1997) 59-77. doi: · Zbl 0870.05033
[4] R. Diestel, Graph Theory (Springer Verlag, New York, 1997). doi:
[5] P. Erd˝os, Maximum induced trees in graphs, J. Combin. Theory Ser. B 41 (1986) 61-79. doi:
[6] R. Focardi, F.L. Luccio and D. Peleg, Feedback vertex set in hypercubes, Inform. Process. Lett. 76 (2000) 1-5. doi: · Zbl 1338.68218
[7] M.L. Furst, J.L. Gross and L.A. Mcgeoch, Finding a maximum genus graph imbedding, J. Assoc. Comput. Mach. 35 (1988) 507-537.
[8] L. Gao, X. Xu, J. Wang, D. Zhu and Y. Yang, The decycling number of generalized Petersen graphs, Discrete Appl. Math. 181 (2015) 297-300. doi: · Zbl 1304.05082
[9] F. Harary, Graph Theory (Academic Press, New York, 1967).
[10] G. Kirchhoff, ¨Uber die Aufl¨osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str¨ome gef¨uhrt wird, Ann. Phys. Chem. 72 (1847) 497-508.
[11] R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations (Plenum Press, New York, 1972) 85-103.
[12] M.Y. Lien, H.L. Fu and C.H. Shih, The decycling number of Pm × Pn, Discrete Math. Algorithms Appl. 3 (2014) 1-9. doi:
[13] D.A. Pike and Y. Zou, Decycling cartesian products of two cycles, SIAM J. Discrete Math. 19 (2005) 651-663. doi: · Zbl 1096.05030
[14] N. Punnim, The decycling number of cubic graphs, Combinatorial Geometry and Graph Theory 3330 (2005) 141-145. doi: · Zbl 1117.05022
[15] N. Punnim, The decycling number of cubic planar graphs, in: Proceedings of the 7th China-Japan Conference on Discrete Geometry, Combinatorics and Graph Theory, Lecture Notes in Comput. Sci. 4381 (2007) 149-161. doi: · Zbl 1149.05315
[16] H. Ren and S. Long, The decycling number and maximum genus of cubic graphs, J. Graph Theory 88 (2018) 375-384. doi: · Zbl 1393.05166
[17] E. Speckenmeyer, On feedback vertex sets and nonseparating independent sets in cubic graphs, J. Graph Theory 12 (1988) 405-412. doi: · Zbl 0657.05042
[18] E. Wei, Y. Liu and Z. Li, Decycling number of circular graphs, ISORA’09 1 (2009) 387-393.
[19] E. Wei and Y. Li, Decycling number and upper-embeddiblity of generalized Petersen graphs, Acta Math. Sinica (Chin. Ser.) 56 (2013) 211-216. · Zbl 1289.05107
[20] N.H. Xuong, How to determine the maximum genus of a graph, J. Combin. Theory Ser. B 26 (1979) 226-232. doi: · Zbl 0403.05035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.