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

B.L. Hartnell1, C.A. Whitehead2
1Saint Mary’s University, Halifax, N.S., Canada B3H 3C3
222 Leyfield Road, Sheffield, $17 3EE, UK

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