A set of vertices of a graph whose removal leaves an acyclic graph is called a decycling set of the graph. The minimum size of a decycling set of a graph G is referred to as the decycling number of G, denoted by δ(G). In this paper, we study the decycling number of the Cartesian product of two paths, δ(Pm-Pn), and obtain several new results. Mainly, we prove that ⌈(m-1)(n-1)+13⌉≤ (Pm □ Pn≤ (m-1)(n-1)+13 +1. Moreover, we obtain the exact value of δ(PmPn) for some classes (modulo 6) of pairs (m, n).
- Decycling number
- feedback vertex number