Jinshan Xie

The decycling number $\phi(G)$ of a graph $G$ is the minimum number of vertices that must be removed in order to eliminate all the cycles in $G$. We first review some known results, and then introduce some new results about decycling numbers of some cross or box-cross product graphs. For general paths $P_{m}$ and $P_{n}$, a sharp lower bound and a sharp upper bound of the decycling number of cross product graph $P_{m}\times P_{n}$ are proved, and for some special paths $P_{m}$ and $P_{n}$, exact decycling numbers of $P_{m}\times P_{n}$ are obtained; for general graphs $G_{1}$ and $G_{2}$, a sharp lower bound and a sharp upper bound of the decycling number of box-cross product graph $G_{1}\boxtimes G_{2}$ are also proved, and for some special graphs $G_{1}$ and $G_{2}$, exact decycling numbers of $G_{1}\boxtimes G_{2}$ are also obtained.