Feedback Arc Number and Feedback Vertex Number of Cartesian Product of Directed Cycles

Abstract EN

For a digraph D, the feedback vertex number τD, (resp.

the feedback arc number τ′D) is the minimum number of vertices, (resp.

arcs) whose removal leaves the resultant digraph free of directed cycles.

In this note, we determine τD and τ′D for the Cartesian product of directed cycles D=Cn1→□Cn2→□…Cnk→.

Actually, it is shown that τ′D=n1n2…nk∑i=1k1/ni, and if nk≥…≥n1≥3 then τD=n2…nk.