Geodesic
New Formulae for the Decycling Number of Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 125-141.

Voir la notice de l'article provenant de la source Library of Science

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 ∇(G). Our results include: (a) For any graph G, ∇ (G) = n - max_T {α (G- E(T)) },where T is taken over all the spanning trees of G and α (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| = 1/k-1 (β (G) + m(S)),where β(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 ∇-set if and only if m(S) is minimum, where ∇-set denotes a decycling set containing exactly ∇(G) vertices of G. This provides a new way to locate ∇(G) for k-regular graphs G. (c) 4-regular graphs G with the decycling number ∇ (G) = β(G)3 are determined.
Keywords: decycling number, independence number, cycle rank, margin number 
@article{DMGT_2019_39_1_a10,
     author = {Yang, Chao and Ren, Han},
     title = {New {Formulae} for the {Decycling} {Number} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {125--141},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a10/}
}
TY  - JOUR
AU  - Yang, Chao
AU  - Ren, Han
TI  - New Formulae for the Decycling Number of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 125
EP  - 141
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a10/
LA  - en
ID  - DMGT_2019_39_1_a10
ER  - 
%0 Journal Article
%A Yang, Chao
%A Ren, Han
%T New Formulae for the Decycling Number of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 125-141
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a10/
%G en
%F DMGT_2019_39_1_a10
Yang, Chao; Ren, Han. New Formulae for the Decycling Number of Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 125-141. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a10/

[1] M.O. Albertson and D.M. Berman, The acyclic chromatic number, Congr. Numer. 17 (1976) 51-69.

[2] S. Bau and L.W. Beineke, The decycling number of graphs, Australas. J. Combin. 25 (2002) 285-298.

[3] L.W. Beineke and R.C. Vandell, Decycling graphs, J. Graph Theory 25 (1997) 59-77. doi: 10.1002/(SICI)1097-0118(199705)25:1$h$59::AID-JGT4$i$3.0.CO;2-H

[4] R. Diestel, Graph Theory (Springer Verlag, New York, 1997). doi: 10.4171/OWR/2007/16

[5] P. Erd˝os, Maximum induced trees in graphs, J. Combin. Theory Ser. B 41 (1986) 61-79. doi: 10.1016/0095-8956(86)90028-6

[6] R. Focardi, F.L. Luccio and D. Peleg, Feedback vertex set in hypercubes, Inform. Process. Lett. 76 (2000) 1-5. doi: 10.1016/S0020-0190(00)00127-7

[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: 10.1016/j.dam.2014.09.005

[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: 10.1142/S1793830914500335

[13] D.A. Pike and Y. Zou, Decycling cartesian products of two cycles, SIAM J. Discrete Math. 19 (2005) 651-663. doi: 10.1137/S089548010444016X

[14] N. Punnim, The decycling number of cubic graphs, Combinatorial Geometry and Graph Theory 3330 (2005) 141-145. doi: 10.1007/978-3-540-30540-8-16

[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: 10.1007/978-3-540-70666-3-16

[16] H. Ren and S. Long, The decycling number and maximum genus of cubic graphs, J. Graph Theory 88 (2018) 375-384. doi: 10.1002/jgt.22218

[17] E. Speckenmeyer, On feedback vertex sets and nonseparating independent sets in cubic graphs, J. Graph Theory 12 (1988) 405-412. doi: 10.1002/jgt.3190120311

[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.

[20] N.H. Xuong, How to determine the maximum genus of a graph, J. Combin. Theory Ser. B 26 (1979) 226-232. doi: 10.1016/0095-8956(79)90058-3.