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

Authors: Xiaohong Chen; Baoyindureng Wu
Journal: Discrete Dynamics in Nature and Society
 (2019)

---

## Abstract

For a digraphD, 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.


---

## Body

## 1. Introduction

LetG=V,E be an undirected graph. A set S⊆VG is called a feedback vertex set of G if G−S contains no cycle. The feedback vertex number of G, denoted by τG, is the cardinality of a minimum feedback vertex set of G. In general, it is NP-hard to determine the feedback vertex number of a graph G [1]. However, it becomes polynomial for specific families of graphs such as interval graphs [2], permutation graphs [3], graphs with maximum degree 3 [4], and k-trees. The readers are referred to [5, 6] for a review of some earlier results and open problems, and [7–9] for some recent results on the feedback vertex number of graphs. Some bounds or exact values are established for various families of graph, for instance, outerplanar graphs [10], grids and butterflies [11], cubic graphs [12, 13], bipartite graphs [14], generalized Petersen graphs [15], regular graphs [16, 17]. Bau et al. [18] investigated the feedback number of grid graphs.Apart from its graph-theoretical importance, the feedback vertex problem has many applications, such as operating system [19, 20], artificial intelligence [21], synchronous distributed systems [22, 23], optical networks [24]. The feedback vertex set and the feedback vertex number are also known as decycling set and the decycling number, respectively, see [25].In 2005, Pike and Zou [26] determined the feedback vertex number of the Cartesian products of two cycles as follows:(1)τCm□Cn=3n2,ifm=43m2,ifn=4mn+23,otherwise.Our main concern in this note is the directed version of the feedback vertex number. A directed graphD is said to be acyclic if it does not contain any directed cycle. A feedback vertex set in a digraph D is a set S of vertices such that D−S is acyclic, and the feedback vertex number of D is the minimum size of such a set is denoted by τD. We denote by νD the number of vertex-disjoint cycles of D. Clearly, τD≥νD for any digraph D. A feedback arc set of a digraph D is a set S of arcs such that D−S is acyclic. The feedback arc number of D, denoted by τ′D, is the cardinality of a minimum feedback arc set of D. We denote by ν′D the number of arc-disjoint cycles of D′. Clearly, τ′D≥ν′D for any digraph D.Not much works were known for the feedback vertex number or the feedback arc number of directed graphs. Lien et al. [27] gave an upper bound for the feedback vertex number of generalized Kautz digraphs. Figueroa et al. [28] investigated the relation for the relationship between the minimum feedback arc set and the acyclic disconnection of a digraph. Even et al. [29] gave a Olognloglogn-approximation algorithm for the feedback vertex problem for a digraph of order n. For planar digraphs, the approximation ratio is not greater than 9/4 [30], and for tournament, it is 2.5 [31]. We refer to [32–34] for more results on feedback vertex set problems for tournaments and bipartite tournaments.The Cartesian productD1□D2□…Dk of directed digraph D1,D2,…,Dk is the digraph with the vertex set VD1×VD2×…VDk, in which there is an arc directed from x1,x2,…,xk to y1,y2,…,yk if and only if there exists an integer j∈1,…,k such that xjyj∈ADj and xi=yi for any other i≠j. For any integer n≥3, Cn→ denotes the directed cycle of order n. Various kinds of properties of Cn1→□Cn2→□…Cnk→ are investigated. Trotter and Erdös [35] give a necessary and sufficient condition for Cn1→□Cn2→ being hamiltonian. Keating [36] gave a necessary and sufficient condition for Cn1→□Cn2→ being decomposed into directed Hamilton cycles. Recently, the previous result is extended by Bogdanowicz [37] with the decomposition into directed cycles of equal length. The domination number [38–41], respectively, the total domination number [42] of the Cartesian product of two directed cycles are investigated.We shall determine the exact values ofτD and τ′D for the Cartesian product of directed cycles D=Cn1→□Cn2→□…Cnk→.


## 2. Main Results

In this section, we denoteCn1→□Cn2→□…Cnk→ by Dn1,n2,…,nk or, simply by D. For convenience, label the vertices of D as x1,x2,…,xk, where xj∈0,1,…,nj−1 for each j∈1,2,…,k. For an integer i∈0,1,…nk−1, let Di be the subgraph of D induced by the set of vertices(2)x1,x2,…,xk−1,i:0≤xj≤nj−1foreachj∈1,…,k−1.It is clear thatDi≅Cn1→□Cn2→□…Cnk−1→ for each i.Theorem 1.
For any
k
≥
2
integers
n
1
,
…
,
n
k
with
n
i
≥
3
for each
i
∈
1
,
…
,
k
,(3)
τ
′
C
n
1
→
□
C
n
2
→
□
…
C
n
k
→
=
n
1
n
2
…
n
k
∑
i
=
1
k
1
n
i
.Proof.
First, we show thatτ′D≥n1n2…nk∑i=1k1/ni by showing that.(4)
ν
′
D
≥
n
1
n
2
…
n
k
∑
i
=
1
k
1
n
i
.We proceed with induction onk. Let k=2. By our notation, Di≅Cn1→ for each i∈0,1,…,n2−1. Note that Di and Dj are vertex-disjoint (and thus arc-disjoint). Moreover, since D\∪i=0n2−1ADi≅n2Cn1→, ν′D≥n1+n2. Now assume that k≥3. Since Di≅Cn1→□Cn2→□…Cnk−1→ for each i∈0,1,…nk−1, by the induction hypothesis,(5)ν′D≥n1n2…nk−1∑i=1k1ni.for eachi∈0,1,…nk−1. After removing these n1n2…nk∑i=1k−11/ni cycles from D, it results in exactly n1n2…nk−1 arc-disjoint directed cycles. This gives(6)ν′D≥n1n2…nk−1nk∑i=1k−11ni+n1n2…nk−1=n1n2…nk∑i=1k1ni.Next we show thatτ′D≤n1n2…nk∑i=1k1ni by finding a feedback arc set of D with cardinality n1n2…nk∑i=1k1/ni. Such a set feedback arc set Ak for Dn1,n2,…,nk is constructed recursively as follows. For convenience, let A1:=n1−1,0. Note that A1 is a feedback arc set of Cn1→. For k≥2, Ak=x1,…,xk−1,jy1,…,yk−1,j:x1,…,xk−1y1,…,yk−1∈Ak−1,0≤j≤nk−1∪x1,…,xk−1,nk−1x1,…,xk−1,0:x1,…,xk−1∈VDk−1. By the above construction and the induction hypothesis,(7)Ak=Ak−1nk+n1n2…nk−1=n1n2…nk−1nk∑i=1k−11ni+n1n2…nk−1=n1n2…nk∑i=1k1ni.Moreover, sinceD\Ak≅Pn1→□Pn2→□…Pnk→ is acyclic, we conclude that Ak is a feedback arc set of D. This proves τ′D≤n1n2…nk∑i=1k1ni.For an illustration, for the case whenk=2, we have D=Cn1→□Cn2→, and A2=n1−1,00,0,n1−1,10,1,…,n1−1,n2−1n2−1,00,n2−10,0,1,n2−11,0,…,n1−1,n2−1n1−1,0, that is, the set of arcs colored in red as shown in Figure 1.Figure 1
The feedback arc setA2 of D=Cn1→□Cn2→.Theorem 2.
For any
k
≥
2
integers
n
1
,
n
2
,
…
,
n
k
with
n
k
≥
…
≥
n
1
≥
3
,(8)
τ
C
n
1
→
→
C
n
2
→
□
…
C
n
k
→
=
n
2
n
3
…
n
k
.Proof.
LetD=Cn1→□Cn2→□…Cnk→.First, we show thatτD≥n2…nk by showing that(9)νD≥n2…nk.We proceed with induction onk. For the case when k=2, Di≅Cn1→ for each i∈0,1,…,n2−1. It follows that D contains n2 vertex-disjoint copies of Cn1→, and thus νD≥n2. Now assume that k≥3. For every integer i∈0,1,…nk−1, Di≅Cn1→□Cn2→□…Cnk−1→, and hence, by the induction hypothesis,(10)νDi≥n2…nk−1.Moreover, sinceDi and Dj are vertex-disjoint for any 0≤i<j≤nk−1, we have(11)νD≥n2…nk−1nk.As an example for the case whenn1=3 and n2=4, we have D=C3→□C4→ and SD=1,00,12,21,3, see Figure 2 for an illustration. Clearly, SD is a feedback vertex set of D with |S2|=4.Figure 2
The feedback vertex setSD of D=C3→□C4→.For anyk≥2, and j∈0,1,…,nk−1, let(12)Sk≔x1,x2,…,xk−1,xk:x1+x2+…+xk≡1modn1,0≤xi≤ni−1.Since for any given value ofx2,…,xk−1,xk with 0≤xi≤ni−1, there exists unique value of x1 with 0≤x1≤n1−1 satisfying x1+x2+…+xk≡1modn1, implying that |Sk|=nknk−1…n2.To show thatSk is a feedback vertex set of D, we consider any directed cycle C→=v1v2…vtv1 of D, where vi=x1i,x2i,…,xki for each i∈1,…,t. Since for each i, vivi+1∈AD, we have(13)x1i+1+x2i+1+…+xki+1≡x1i+x2i+…+xki+1modn1.Moreover, sincet≥n1=minn1,n2,…,nk, there exists an integer j∈1,…,t such that(14)x1j+x2j+…+xkj≡1modn1,implying thatvj=x1j,x2j,…,xkj∈Sk, and thus Sk is a feedback vertex set of D. This proves(15)τD≤n2n3…nk.


## 3. Conclusion

In this note, we determined the two important parametersτ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.



---

*Source: 7028573-2019-12-16.xml*