On decycling and forest numbers of Cartesian products of trees

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 |V(T)|-1$ and the equality cases characterized. For prisms over trees, it is proved that $\nabla (T\square K_2)=\hat{I}{\pm }^{\prime }(T)$, and for arbitrary graphs $G_1$ and $G_2$, it is proved that $\nabla (G_1\square G_2)\ge \hat{I}{\pm }^{\prime }(G_1)\hat{I}{\pm }^{\prime }(G_2)$, where $\hat{I}{\pm }^{\prime }$ is the matching number.