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)].

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