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 $\varphi (G)$, is the cardinality of a smallest decycling set in $G$. We obtain sharp bounds on the value of the Cartesian product $\varphi (G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{K}_2)$ and determine its value in the case where $G$ is the grid graph $P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n$, for all $m,n\ge 2$.