The decycling number of Pm □ Pn

Min Yun Lien, Hung Lin Fu, Chie Huai Shih

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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

Original languageEnglish
Article number1450033
JournalDiscrete Mathematics, Algorithms and Applications
Issue number3
StatePublished - 1 Sep 2014


  • Decycling number
  • feedback vertex number
  • grids

Fingerprint Dive into the research topics of 'The decycling number of P<sub>m</sub> □ P<sub>n</sub> ∗'. Together they form a unique fingerprint.

Cite this