Ma HongxiaZhao Juan Feng Yanqiu

(College of Preparatory,Xinjiang Normal University,Urumqi 830017,China)

Abstract Let γ*(D)denote the twin domination number of digraph D and let Cm□Cn denote the Cartesian product of the directed cycle Cm and Cn,for m,n≥2.In this paper,we give a lower bound for γ*(Cm□Cn)and we determine the exact values of γ*(Cm□Cn)when m,n≡0(mod 3)and when m≡2(mod 3).

Key words Digraph Twin domination number Cartesian product Directed cycle

1 Introduction

LetD=(V,A)be a finite digraph without loops and multiple arcs,whereV=V(D)is the vertex set andA=A(D)is the arc set.For a vertexdenote the set of out-neighbors and in-neighbors ofv,respectively.The out-degree and in-degree ofvare defined byA digraphDis calledr-regular iffor any verticesvinV(D).Given two verticesuandvinV(D),we say thatuout-dominatesv(orvin-dominatesu)ifu=vorA vertexvout-dominates all vertices inA setS?V(D)is called an out-dominating(in-dominating)set ofDifSout-dominates(in-dominates)V(D).The out-domination number ofD,denoted byγ+(D),is the minimum cardinality of an out-dominating set ofD.The in-domination number is defined analogusly.Some results of twin domination in digraphs has been obtained in[1–3].A setis a twin dominating set ofDif for any vertexv∈V?S,there existu,w∈S(possiblyu=w)such that arcsuv,vw∈A(D).The twin domination number ofD,denoted byγ*(D),is the minimum cardinality of a twin dominating set ofD.Clearly,γ+(D)≤γ*(D).

LetD1=(V1,A1)andD2=(V2,A2)be two digraphs which have disjoint vertex setsV1={x1,x2,...,xn1}andV2={y1,y2,...,yn2}and disjoint arc setsA1andA2,respectively.The Cartesian productD=D1□D2has vertex setV=V1×V2and(xi,yj)(xi′,yj′)∈A(D)if and only if one of the following holds:

(a)xi=xi′andyjyj′∈A2?

(b)yj=yj′andxixi′∈A1.

For any fixed vertexyi∈V2,the subdigraphofDhas vertex seand arc setIt is clear thatD1yi～=D1.Similarly,for any fixed vertexxi∈V1,the subdigraphD2xiofDhas vertex setand arc setIt is clear thatTwin domination in digraph is a fundamental and interesting concept.[4–8]presented some related works of out-domination number of the Cartesian product and strong product of directed cycles and directed paths.However,to date no research about the twin domination number has been done for the Cartesian product of directed cycles.

In this paper,we study the twin domination number ofCm□Cn,obtain the lower bound ofγ*(Cm□Cn),and give the following exact values

2 Main results

We emphasize that the vertices of a directed cycleCmare always denoted by the integers{0,1,...,m?1}considering modulom.There is an arcxyfromxtoyinCmif and only ify=x+1(modm).For any vertex(i,j)∈V(Cm□Cn),

the first digit and second digit are considered modulomandn,respectively.

LetCm□Cndenote the Cartesian product ofCmandCn.Observe that the vertices ofare out-dominated by vertices ofand in-dominated by vertices of1}.Especially,the vertices ofare out-dominated by vertices ofand in-dominated by vertices of

Lemma 2.1Letm,n≥2,and

(i)Ifm≡0(mod 3),thenγ*(Cm□Cn)≥nk1?

(ii)Ifm≡1(mod 3),then

(iii)Ifm≡2(mod 3),thenγ*(Cm□Cn)≥nk1+n.

ProofLetSbe a twin domination set ofCm□CnandObserve that each of the vertices ofnot only in-dominates two vertices inbut also out-dominates one vertex inthe vertices ofare only out-dominated by vertices of

Now we turn to investigate the twin domination number ofCm□Cn.

Firstly,we consider the casem≡0(mod 3)andn≡0,2(mod 3).

Define a set as follow(see Figure 1):

Figure 1 The set S1

S1={(3j,i):i≡0(mod 3);(3j+1,i):i≡1(mod 3);(3j+2,i):i≡2(mod 3);wherej∈{0,1,...,k1?1}}.

Theorem 2.1Letm,n≥2 andthen

ProofIfn≡0(mod 3),then we can assume thatn=3k2.Based on Lemma 2.1,we can obtain thatγ*(Cm□Cn)≥3k1k2.Clearly,S1is a twin dominating set ofCm□Cn,and|S1|=3k1k2.

Ifn=3k2+2,then we deduce thatγ*(Cn□Cm)≥3k1k2+3k1from Lemma 2.1.Obviously,S1∪{(3j+2,0)|j∈{0,1,...,k1?1}}is a twin dominating set ofCm□Cnand|S1∪{(3j+2,0)|j∈{0,1,...,k1?1}}|=k1(3k2+2)+k1=3k1k2+3k1.

Secondly,we consider the casem≡2(mod 3).

Theorem 2.2Letm=3k1+2,

(i)Ifn=3k2+2 andk2≥k1,thenγ*(Cm□Cn)=3k1k2+2k1+3k2+2?(Ifk2≤k1,we can obtain an analogous conclusion).

(ii)Ifn=3k2+1 and 2k2≥k1,thenγ*(Cm□Cn)=3k1k2+k1+3k2+1.

ProofFirstly,we assumen=3k2+2.Then by Lemma 2.1,we haveγ*(Cm□Cn)≥3k1k2+2k1+3k2+2.Without loss of generality,we assume thatn≥m,in other words,k2≥k1.Define the following subsets ofV(Cm□Cn):

LetS2=Xi∪Y.We first show thatS2is an out-dominating set ofCm□Cn.

For eachi,1≤i≤m?4,note that the vertices ofare out-dominated by vertices inXiandXi?1.Clearly,all the vertices ofare out-dominated by the vertices inXm?4andY,wheni>m?3,the vertices ofare out-dominated by the vertices inY.Particularly,the vertices ofare out-dominated by vertices inX0andY.It follows thatS2is an out-dominating set ofCm□Cn.

In the following,we show thatS2is also an in-dominating set ofCm□Cn.For eachi,0≤i≤m?5,we see that all vertices ofare in-dominated by vertices inXiandXi+1.Particularly,the vertices ofare in-dominated by vertices inX0andY.ThereforeS2is an in-dominating set ofCm□Cn.

From above,we conclude thatS2is a twin dominating set ofCm□Cnwith cardinality 3k1k2+2k1+3k2+2.

As an example,Figure 2 shows a twin dominating sets ofC11□C14.

Figure 2 A twin dominating set of C11□C14

Secondly,we assumen=3k2+1.

It is evident from Lemma 2.1 thatγ*(Cm□Cn)≥3k1k2+k1+3k2+1.Assume that,that is 2k2≥k1.

Ifk1is even,thenmis even.Define some sets as follows:

Y={(3j+1,i)|j∈{0,1,...,k1},i≡1(mod 3)}∪{(0,i),(3j+2,i)|j∈{0,1,...,k1?1},i≡2(mod 3)}∪{(1,i),(3j,i)|j∈{1,2,...,k1},i≡0(mod 3)},where

It is clear that all the vertices inX0∪Xicould out-dominate the vertices fromMoreover,the vertices ofare out-dominated by the vertices inandY.Whenthe vertices inYcould dominate all the vertices ofI n particular,the vertices ofare out-dominated by the vertices inX0andY.SoS3is an out-dominating set ofCm□Cn.Similarly,we can show thatS3is also an in-dominating set ofCm□Cn.ThereforeS3is a twin dominating set ofCm□Cn,and|S3|=n(k1+1)=3k1k2+k1+3k2+1.

As an example,Figure 3 shows a twin dominating sets ofC8□C13.

Ifk1is odd,then define some sets as follows:

Y′={(3j+1,i)|j∈{0,1,...,k1},i≡1(mod 3)}∪{(0,i),(3j+2,i)|j∈{0,1,...,k1?1},i≡2(mod 3)}∪{(1,i),(3j,i)|j∈{1,2,...,k1},i≡0(mod 3)},where

Similarly,whenwe have thatX0∪Xi′is a twin dominating set ofCm□Cn,and whenis a twin dominating set ofCm□Cn.This completes the proof of the Theorem.

As an example,Figure 4 shows a twin dominating sets ofC11□C13.

Figure 3 A twin dominating set of C8□C13

Figure 4 A twin dominating set of C11□C13