×

zbMATH — the first resource for mathematics

The decycling number of generalized Petersen graphs. (English) Zbl 1304.05082
Summary: A subset \(F \subset V(G)\) is called a decycling set if the subgraph \(G - F\) is acyclic. The minimum cardinality of a decycling set is called the decycling number of \(G\), which is proposed first by L. W. Beineke and R. C. Vandell [J. Graph Theory 25, No. 1, 59–77 (1997; Zbl 0870.05033)]. We use \(\nabla(P_{n, k})\) to denote the decycling number of the generalized Petersen graphs \(P_{n, k}\). This paper proves that
\[ \nabla(P_{n, k}) = \begin{cases} \lceil \frac{n + 1}{2} \rceil,&\text{if } n \neq 2 k, \\ \lceil \frac{k + 1}{2} \rceil, &\text{if } n = 2 k.\end{cases} \]

MSC:
05C38 Paths and cycles
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bafna, V.; Berman, P.; Fujito, T., A 2-approximation algorithm for the undirected feedback vertex set problem, SIAM J. Discrete Math., 12, 289-297, (1999) · Zbl 0932.68054
[2] Bau, S.; Beineke, L. W., The decycling number of graphs, Australas. J. Combin., 25, 285-298, (2002) · Zbl 0994.05079
[3] Beineke, L. W.; Vandell, R. C., Decycling graphs, J. Graph Theory, 25, 59-77, (1997) · Zbl 0870.05033
[4] Erdös, P.; Saks, M.; Sós, V. T., Maximum induced trees in graphs, J. Combin. Theory Ser. B, 41, 61-79, (1986) · Zbl 0603.05023
[5] Focardi, R.; Luccio, F. L.; Peleg, D., Feedback vertex set in hypercubes, Inform. Process. Lett., 76, 1-5, (2000) · Zbl 1338.68218
[6] Garey, M. R.; Johnson, D. S., (Computers and Intractability, A Guide to the Theory of NP-Completeness, A Series of Books in the Mathematical Sciences, (1979), W. H. Freeman and Co.), x+338
[7] Karp, R. M., Reducibility among combinatorial problems, (Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, 1972), (1972), Plenum), 85-103
[8] Kheddouci, H.; Togni, O., Bounds for minimum feedback vertex sets in distance graphs and circulant graphs, Discrete Math. Theoret. Comput. Sci., 10, 57-70, (2008) · Zbl 1153.05023
[9] Wang, F.-H.; Wang, Y.-L.; Chang, J.-M., Feedback vertex sets in star graphs, Inform. Process. Lett., 89, 203-208, (2004) · Zbl 1176.05081
[10] Wang, J.; Xu, X.-R.; Zhu, D.-J.; Gao, L.-Q.; Xu, J.-M., On the bounds of feedback numbers of \((n, k)\)-star graphs, Inform. Process. Lett., 112, 473-478, (2012) · Zbl 1243.05115
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.