# zbMATH — the first resource for mathematics

Decycling number and upper-embeddibility of generalized Petersen graphs. (Chinese. English summary) Zbl 1289.05107
Summary: Given a graph $$G=(V, E),\;S\subseteq V$$, the minimal number of $$S$$ whose removal eliminates all the cycles in $$G$$ is called the decycling number, denoted as $$\nabla(G)$$. The problem of determinating the decycling number of a graph is NP-complete. Bau and Beineke proposed the following question: which cubic graphs of order $$2n$$ have decycling number $$\lceil \frac{n+1}2\rceil$$? In this paper, we prove that generalized Petersen graph $$P(n, k)$$ is such a class of graphs. Based on this result, we prove that $$P(n, k)$$ is upper-embeddable which generalizes a result of D. Ma and H. Ren [Northeast. Math. J. 24, No. 3, 189–195 (2008; Zbl 1199.05072)].

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles