On Maximum Induced Forests of the Balanced Bipartite Graphs

The decycling number $\mathrm{\nabla }(G)$ of a graph $G$ is the minimum number of vertices that must be removed to eliminate all cycles in $G$. The forest number $f(G)$ is the maximum number of vertices that induce a forest in $G$. So $\mathrm{\nabla }(G)+f(G)=\mathrm{\mid }V(G)\mathrm{\mid }$. For the Cartesian product $T\mathrm{\square }{T}^{\mathrm{\prime }}$ of trees $T$ and $T^{\mathrm{\prime }}$ it is proved that $\mathrm{\nabla }(S_n\mathrm{\square }{S}_{n^{\mathrm{\prime }}})\le \mathrm{\nabla }(T\mathrm{\square }{T}^{\mathrm{\prime }})$, thus resolving the conjecture of Wang and Wu asserting that $f(T\mathrm{\square }{T}^{\mathrm{\prime }})\le f(S_n\mathrm{\square }{S}_{n^{\mathrm{\prime }}})$. It is shown that $\mathrm{\nabla }(T\mathrm{\square }{T}^{\mathrm{\prime }})\ge \min \{\mathrm{\mid }V(T)\mathrm{\mid },\mathrm{\mid }V(T^{\mathrm{\prime }})\mathrm{\mid }\}-1$ and the equality cases characterized. For prisms over trees, it is proved that $\mathrm{\nabla }(T\mathrm{\square }{K}_2)={\alpha }^{\mathrm{\prime }}(T)$, and for arbitrary graphs $G_1$ and $G_2$, it is proved that $\mathrm{\nabla }(G_1\mathrm{\square }{G}_2)\ge {\alpha }^{\mathrm{\prime }}(G_1){\alpha }^{\mathrm{\prime }}(G_2)$, where ${\alpha }^{\mathrm{\prime }}$ is the matching number.