zbMATH — the first resource for mathematics

A new formula for the decycling number of regular graphs. (English) Zbl 1370.05105
Summary: The decycling number \(\nabla(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 \(\nabla(G)\) vertices of \(G\) is called a \(\nabla\)-set. For any decycling set \(S\) of a \(k\)-regular graph \(G\), we show that \(| S | = \frac{\beta(G) + m(S)}{k - 1}\), where \(\beta(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 \(\nabla\)-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 \(\frac{\beta(G) + \xi(G)}{2}\). Hence \(\nabla(G) = \lceil \frac{\beta(G)}{2} \rceil\) for a 3-regular upper-embeddable graph \(G\), which concludes the results in [L. Gao et al., Discrete Appl. Math. 181, 297–300 (2015; Zbl 1304.05082); E. Wei and Y. Li, Acta Math. Sin., Chin. Ser. 56, No. 2, 211–216 (2013; Zbl 1289.05107)] and solves two open problems posed by S. Bau and L. W. Beineke [Australas. J. Comb. 25, 285–298 (2002; Zbl 0994.05079)]. Considering an algorithm by M. Furst, J. L. Gross and L. A. McGeoch [“Finding a maximum genus graph imbedding”, J. Assoc. Comput. Mach. 35, No. 3, 523–534 (1988; doi:10.1145/44483.44485)], 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 E. Speckenmeyer [J. Graph Theory 12, No. 3, 405–412 (1988; Zbl 0657.05042)]. As for a 4-regular graph \(G\), we show that for any \(\nabla\)-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 \(\nabla(G) = \lceil \frac{\beta(G)}{3} \rceil\). On the other hand, if \(G\) is a loopless graph on \(n\) vertices with maximum degree at most 4, then \[ \nabla(G) \leq \begin{cases} \frac{n + 1}{2}, & \text{if G is 4-regular}, \\ \frac{n}{2}, & \text{otherwise}. \end{cases}. \] The above two upper bounds are tight, and this makes an extension of a result due to N. Punnim [Thai J. Math. 4, No. 1, 145–161 (2006; Zbl 1156.05317)].

05C35 Extremal problems in graph theory
Full Text: DOI
[1] M. Albertson, D. Berman, The acyclic chromatic number, Congr. Numer., 17(1976), 51-69.. · Zbl 0344.05116
[2] S. Bau, L. Beineke, The decycling number of graphs, Australas. J. Combin., 25(2002), 285-298.. · Zbl 0994.05079
[3] S. Bau, N. Wormald, S. Zhou, Decycling numbers of random regular graphs, Random Structures Algorithms, 21(2002), no. 3-4, 397-413.. · Zbl 1012.05099
[4] L. Beineke, R. Vandell, Decycling graphs, J. Graph Theory, 25(1997), no. 1, 59-77.. · Zbl 0870.05033
[5] R. Diestel, Graph Theory, Springer-Verlag, New York, 1997..
[6] P. Erdös, M. Saks, V. Sós, Maximum induced trees in graphs, J. Combin. Theory Ser. B, 41(1986), 61-79..
[7] R.Focardi, F.Luccio, D.Peleg, Feedback vertex set in hypercubes, Inform.Process.Lett., 76(2000), no.1-2, 1-5.. · Zbl 1338.68218
[8] M.Furst, J.Gross, L.Mcgeoch, Finding a maximum genus graph imbedding, J.Assoc.Comput.Mach, 35(1988), no.3, 523-534..
[9] L.Gao, X.Xu, J.Wang, D.Zhu, Y.Yang, The decycling number of generalized Petersen graphs, Discrete Appl. Math., 181(2015), 297C300.. · Zbl 1304.05082
[10] F. Harary, Graph Theory, Academic Press, New York, 1967..
[11] G.Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. Chem., 72(1847), 497-508..
[12] R.Karp, Reducibility among combinatorial problems, Complexity of computer computations, (Proc. Sympos., IBM Thomas J.Watson Res.Center, Yorktown Heights, N.Y., 1972), 85C103.Plenum, New York, 1972.. · Zbl 1187.90014
[13] Y.Liu, The maximum orientable genus of a graph, Sci.Sinica, Special Issue on Math., 1979, Special Issue II on Math., 41-55..
[14] D.Ma, Embedding of graphs on surface and crossing numbers, Master thesis, Shanghai, East China Normal University, 2004..
[15] D.Pike, Y.Zou, Decycling cartesian products of two cycles, SIAM J.Discrete Math., 19(2005), no.3, 651-663.. · Zbl 1096.05030
[16] N. Punnim, The decycling number of cubic graphs, Combinatorial Geometry and Graph Theory, 141-145, Lecture Notes in Comput. Sci., 3330, Springer, Berlin, 2005.. · Zbl 1117.05022
[17] N.Punnim, The decycling number of cubic planar graphs, Discrete Geometry, Combinatorics and Graph Theory, 149-161, Lecture Notes in Comput. Sci., 4381, Springer, Berlin, 2007.. · Zbl 1149.05315
[18] N. Punnim, The decycling number of regular graphs, Thai J. Math., 4(2006), 145-161.. · Zbl 1156.05317
[19] H. Ren, S. Long, The decycling number and maximum genus of cubic graphs. (Submitted). · Zbl 1393.05166
[20] E.Speckenmeyer, On feedback vertex sets and nonseparating independent sets in cubic graphs, J. Graph Theory, 12(1988), no. 3, 405-412.. · Zbl 0657.05042
[21] E. Wei, Y. Liu, Z. Li, Decycling number of circular graphs, ISORA’09, (2009), 387-393..
[22] E.Wei, Y.Li, Decycling number and upper-embeddiblity of generalized Petersen graphs, Acta Math. Sinica(Chin. Ser.), 56(2013), no. 2, 211-216.. · Zbl 1289.05107
[23] N.Xuong, How to determine the maximum genus of a graph, J.Combin.Theory Ser.B, 26(1979), 217-225.. · 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.