Feedback arc number and feedback vertex number of Cartesian product of directed cycles (Q2296552)

Summary: For a digraph \(D\), the feedback vertex number \(\tau \left(D\right)\), (resp. the feedback arc number \(\tau' \left(D\right))\) is the minimum number of vertices, (resp. arcs) whose removal leaves the resultant digraph free of directed cycles. In this note, we determine \(\tau \left(D\right)\) and \(\tau' \left(D\right)\) for the Cartesian product of directed cycles \(D = \overrightarrow{C_{n_1}} \square \overrightarrow{C_{n_2}} \square \cdots \overrightarrow{C_{n_k}} \). Actually, it is shown that \(\tau' \left(D\right) = n_1 n_2 \cdots n_k \sum_{i = 1}^k 1 / n_i\), and if \(n_k \geq \dots \geq n_1 \geq 3\) then \(\tau \left(D\right) = n_2 \ldots n_k\).