On Maximum Induced Forests of the Balanced Bipartite Graphs

Abstract

The decycling number $\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 $\nabla (G)+f(G)=|V(G)|$. For the Cartesian product $T\square T^{\prime }$ of trees $T$ and $T^{\prime }$ it is proved that $\nabla (S_n\square S_{n^{\prime }})\le \nabla (T\square T^{\prime })$, thus resolving the conjecture of Wang and Wu asserting that $f(T\square T^{\prime })\le f(S_n\square S_{n^{\prime }})$. It is shown that $\nabla (T\square T^{\prime })\ge \min \{|V(T)|,|V(T^{\prime })|\}-1$ and the equality cases characterized. For prisms over trees, it is proved that $\nabla (T\square K_2)={\alpha }^{\prime }(T)$, and for arbitrary graphs $G_1$ and $G_2$, it is proved that $\nabla (G_1\square G_2)\ge {\alpha }^{\prime }(G_1){\alpha }^{\prime }(G_2)$, where ${\alpha }^{\prime }$ is the matching number.