Decycling the Cartesian Product of a Bipartite Graph with \(K_{2}\)

Abstract

A decycling set in a graph \( G \) is a set \( D \) of vertices such that \( G – D \) is acyclic. The decycling number of \( G \), denoted \( \phi(G) \), is the cardinality of a smallest decycling set in \( G \). We obtain sharp bounds on the value of the Cartesian product \( \phi(G \square K_2) \) and determine its value in the case where \( G \) is the grid graph \( P_m \square P_n \), for all \( m, n \geq 2 \).