Decycling Cartesian Products of Two Cycles

Abstract

The decycling number $\nabla(G)$ of a graph G is the smallest number of vertices which can be removed from G so that the resultant graph contains no cycles. In this paper, we study the decycling number for the family of graphs consisting of the Cartesian product of two cycles. We completely solve the problem of determining the decycling number of $C_m \square C_n$ for all m and n. Moreover, we find a vertex set T that yields a maximum induced tree in $C_m\square C_n$.