有向图字典式积的双控制数(英文)

摘 要 令γ*（D）表示有向DD的双控制数，Dm[Dn]表示有向图Dm和Dn的字典式积，其中Dm，Dn的阶数m，n分别大于等于2.本文首先给出Dm[Dn]的双控制数的上下界，然后确定如下有向图的双控制数的确切值：Dm[Kn]； Km[Dn]； Km1，m2，…，mt [Dn]； Cm[Dn]； Pm[Cn]及Pm[Pn].

关键词 双控制数；字典式积；有向图

Let D=（V（D），A（D）） be a finite digraph without loops and multiple arcs where V（D） is the vertex set and A（D） is the arc set. For a vertex v∈V（D）， N+D（v） and N-D（v） denote the sets of outneighbors and inneighbors， respectively， of v， d+D（v） =|N+D（v）| and d-D（v） =|N-D（v）| denote the outdegree and indegree of v in D， respectively. A digraph D is rregular if d+D（v）=d-D（v）=r for any vertex v in D. Given two vertices u and v in D， we say that u outdominates v if u=v or uv∈A（D）， and v indominates u if u=v or uv∈A（D）. Let N+D[v]=N+D（v）∪{v}. A vertex v outdominates all vertices in N+D[v]. A set SV（D） is an outdominating set of D if S outdominates all vertices in V（D）. The outdomination number of D， denoted by γ+（D）， is the minimum cardinality of an outdominating set of D. In the same way， the indomination number γ-（D） is the minimum cardinality of an indominating set of D. Some results of twin domination in digraphs have been obtained in [1～6]. A set SV（D） is a twin dominating set of D if each vertex of D is either in S or both an outneighbour of some vertex in S and an inneighbour of some （possibly distinct） vertex in S. The twin domination number of D， denoted by γ*（D）， is the minimum cardinality of a twin dominating set of D. Clearly， if S is a twin dominating set， then S is a n outdominating set and indominating set of D， thus γ*（D）≥γ+（D）≥1 and γ*（D）≥γ-（D）≥1.

Let Dm=（V（Dm），A（Dm）） and Dn=（V（Dn），A（Dn）） be two digraphs which have disjoint vertex sets V（Dm）={x0，x1，…，xm-1} and V（Dn）={y0，y1，…，yn-1} and disjoint arc sets A（Dm） and A（Dn）， respectively. The lexicographic product Dm[Dn] of Dm and Dn has vertex set V（Dm）×V（Dn）={（xi，yj）|xi∈V（Dm），yj∈ Vn} and （xi，yj）（xi′，yj′）∈A（Dm[Dn]） if one of the following holds：

（a） xixi′∈A（Dm）；（b） xi=xi′ and yjyj′∈A（Dn）.

For any fixed vertex yj∈V（Dn）， the subdigraph Dyjm of Dm[Dn] has vertex set V（Dyjm）={（xi，yj）： for any xi∈V（Dm）}， and arc set A（Dyjm）={（xi，yj）（xi′ ，yj）：xixi′∈A（Dm）}. It is clear that DyjmDm. Similarly， for any fixed vertex xi∈V（Dm）， the subdigraph Dxin of Dm[Dn] has vertex set V（Dxin）={（xi，yj）： for any yj∈V（Dn）}， and arc set A（Dxin）={（xi，yj）（xi，yj′ ）：yjyj′∈A（Dn）}. It is clear that DxinDn.

In recent years， the domination number of some digraphs has been investigated in [7～16]. However， to date few research about twin domination number has been done for lexicographic product of digraphs. In this paper， we study the twin domination number of Dm[Dn]. Firstly， we give the upper and lower bound of the twin domination number of Dm[Dn]， and then determine the exact values of the twin domination number of digraphs： Dm[Kn]；Km[Dn]；Km1，m2；…；mt [Dn]； Cm[Dn]； Pm[Cn] and Pm[Pn].

1 Main results

Let Km，Cm，Pm be directed cycle， directed path， complete digraph， respectively. We have γ*（Km）=γ+（Km）=γ-（Km）=1，γ*（Cm）=γ+（Cm）=γ-（Cm）=「m2，γ*（Pm）=「m+12，γ+（Pm）=γ-（Pm）=「m2.

Lemma 1 For any m，n≥2， then γ*（Dm）≤γ*（Dm[Dn]）≤γ*（Dm）γ*（Dn）.

Proof We first prove that γ*（Dm[Dn]）≥γ*（Dm）. Let S be a minimum twin dominating set of Dm[Dn]， so |S|=γ*（Dm[Dn]）. Since Dyjm is the subdigraph of Dm[Dn]， for any yj∈V（Dn）， S twin dominates every vertex of Dyjm. Thus γ*（Dyjm）≤|S|. Moreover DyjmDm， then γ*（Dyjm）=γ*（Dm）， where yj∈V（Dn）. Hence γ*（Dm[Dn]） ≥γ*（Dm）.

Now we prove that γ*（Dm）γ*（Dn）≥γ*（Dm[Dn]）. Let S1={xi1，…，xit} be a minimum twin dominating set of Dm. Let S2={yj1，…，yjw} be a minimum twin dominating set of Dn. Set S′={（xik，yjl）|xik∈S1，yjl∈S2}. For any vertex （xi，yj）∈V（Dm[Dn]）， if xi∈S1 and yj∈S2， then （xi，yj）∈S′. If xi∈S1 and yjS2， there must exist yjl， yjl′ ∈S2， such that yjlyj， yjyjl′∈A（Dn）. Since （xi，yjl）（xi，yj），（xi，yj）（xi，yjl′ ）∈A（Dm[Dn]） and （xi，yjl ），（xi，yjl′）∈S′， （xi，yj） is twin dominated by S′. If xiS1， there must exist xik， xik′∈S1 such that xikxi， xixik′∈A（Dm）， and there must exist yr∈S2 such that （xik，yr）（xi，yj），（xi，yj）（xik′ ，yr）∈A（Dm[Dn]） and （xik，yr）， （xik′ ，yr）∈S′， so （xi，yj） is twin dominated by S′.

Therefore， S′ is a twin dominating set of Dm[Dn] and |S′|=|S1||S2|=γ*（Dm）γ*（Dn）. Thus， γ*（Dm[Dn]） ≤γ*（Dm）γ*（Dn）.

Clearly， the following theorem is obtained from Lemma 1.

Theorem 1 For any m，n≥2， then γ*（Dm[Dn]）=γ*（Dm） if and only if γ*（Dn）=1.

According to Theorem 1， the following theorem is obvious.

Theorem 2 For any m，n≥2， then γ*（Dm[Kn]）=γ*（Dm）.

Theorem 3 For any complete digraph Km and digraph Dn， then

γ*（Km[Dn]）=1 if γ*（Dn）=1；2 if γ*（Dn）≥2.

Proof By Lemma 1 and Theorem 1， it is clear that γ*（Km[Dn]）=1 if γ*（Dn）=1. It is easy to see that S={（x0，y0）} is a twin dominating set of Km[Dn]， where {y0} is a twin dominating set of Dn.

If γ*（Dn）≥2， we assume that γ*（Km[Dn]）=1. Let S be a twin dominating set of Km[Dn] with vertex set {（xi，yj）}， since γ*（Dxin）=γ*（Dn）≥2， we find that there exists at least one vertex in Dxin is not twin dominated by S， where xi∈V（Km）， a contradiction. Thus， γ*（Km[Dn]）≥2. Let S′={（x0，y0），（x1，y0）}， we see that S′ is a twin dominating set of Km[Dn] and |S′|=2.

Let Km1，m2，…，mt be the complete tpartite digraphs. The next Theorem is obtained by Lemma 1 and Theorem 3.

Theorem 4 Let mi≥1， for any i∈{1，2，…，t}. Then

γ*（Km1，m2，…，mt [Dn]）=1 if γ*（Dn）=1 and there exists i such that mi=1；

2 otherwise.

We emphasize that vertices of a directed cycle Cn are always denoted by the integers {0，1，…，n-1}， considering modulo n， throughout this paper. There is an arc xy from x to y in Cn if and only if yx+1（mod n）. For the following addition， we always consider modulo n.

Theorem 5 For m，n≥2， we have

γ*（Cm[Dn]）=

「m2if γ*（Dn）=1；

「2m3 if γ+（Dn）=γ-（Dn）=1 and γ*（Dn）≥2；

motherwise.

Proof If γ*（Dn） = γ+（Dn）= γ-（Dn）=1， by Theorem 1， we can obtain that γ*（Cm[Dn]） =γ*（Cm）=「m2. Note that S={（2i，y0）|i∈{0，1，…，「m2-1}} is a twin dominating set of Cm[Dn]， and |S|=「m2.

Let S be a minimum twin dominating set of Cm[Dn] and bi=|S∩Din|， where i∈V（Cm）. Note that there are not two consecutive integers modulo n，s and s-1， such that bs=bs-1=0.

Now we consider two cases.

Case 1 γ+（Dn）= γ-（Dn）=1 and γ*（Dn）≥2.

If bi=0， then bi-1≥1 and bi+1≥1； if bi=1， then bi-1≥0 and bi+1≥1； if bi≥2， then bi-1≥0 and bi+1≥0. Thus we obtain that bi+bi+1+bi-1≥2. That is 3∑m-1i=0bi≥2m. Hence ∑m-1i=0bi≥「2m3.

Let {yj1} and {yj2} be outdominating set and indominating set of Dn， respectively. Set

S1={（3s+2，yj1）|s∈{0，1，…，m3-1}}，

S2={（3t，yj2）|t∈{0，1，…，「m3-1}}，

S3={（m-1，yj2）}.

When m0，1 （mod 3）， if i0 （mod 3）， then the vertices of Din are outdominated by S1 and indominated by S2， respectively； if i1 （mod 3）， then the vertices of Din are outdominated by S2 and indominated by S1， respectively； if i2 （mod 3）， then the vertices of Din are outdominated by S1 and indominated by S2， respectively. Thus S1∪S2 is a twin dominating set of Cm[Dn] when m0，1 （mod 3） and |S1∪S2|=「2m3.

When m2 （mod 3）， observe that the vertices of Din are twin dominated by S1∪S2 for i∈{0，1，…，m-2}； the vertices of Dm-1n are outdominated by S2 and indominated by S3， respectively. Thus S1∪S2∪S3 is a twin dominating set of Cm[Dn] when m2 （mod 3） and |S1∪S2∪S3|=「2m3.

Case 2 γ*（Dn）≥2 and γ+（Dn）≥2 or γ-（Dn）≥2.

Without loss of generality， we assume that γ+（Dn）≥2. It follows that γ-（Dn）≥1， that is γ+（Dn）≥γ-（Dn）. In this case， let J={i|i∈{0，1，…，m-1}} such that bi=0 and let J′={i|i-1∈J}. It is easy to see that J∩J′=.

If bi=0， in order to outdominate vertices of Di+1n and indominate vertices of Di-1n， then bi+1≥γ+（Dn） and bi-1≥γ-（Dn）. Thus， bi+bi+1+bi-1 ≥γ+（Dn）+γ-（Dn）≥3. Therefore 3∑m-1i=0bi≥3m and hence ∑m-1i=0bi≥m.

If 1≤bi≤2， it is easy to see that bi+bi-1≥2， and bi+1≥0. In addition， if i∈J， bi+bi+1≥γ+（Dn）. When bi+1=0， ∑m-1i=0bi=∑i∈J∪J′bi+

∑iJ∪J′bi≥|J|γ+（Dn）+（m-2）|J|≥m. When bi+1≥1， bi+bi+1+bi-1≥3. Hence ∑m-1i=0bi≥m. If bi≥3， then bi+bi+1+bi-1≥3， ∑m-1i=0bi≥m.

From above，∑m-1i=0bi≥m. We find that S1={（0，y0），（1，y0），…，（m-1，y0）} is a twin dominating set of Cm[Dn]， and |S1|=m. Therefore， γ*（Cm[Dn]） = m. The proof is completed.

For covenience， let Pm be a directed path with vertex set {0，1，…，m-1} in the sequel.

Theorem 6 Let m，n≥2， then

γ*（Pm[Cn]）=

「m+12「n2， if 2≤n≤4 or m=3；

2「n2+m-2，otherwise.

Proof Let S be a minimum twin dominating set of Pm[Cn] and for any i∈V（Pm）， let bi=|S∩Cin|. Note that there do not exist two consecutive integers， s and s+1， such that bs=bs+1=0， where 0≤s≤m-2. In order to twin dominate vertices of C0n and Cm-1n， then b0≥γ+（Cn）=「n2 and bm-1≥γ-（Cn）=「n2.

Let J={i|i∈{0，1，…，m-1}} such that bi=0 and let J′={i|i-1∈J}. It is easy to see that J∩J′= and 0≤|J|≤「m-22 . If bi=0， in order to outdominate every vertices of Ci+1n， then bi+1≥γ+（Cn）=「n2. Thus， bi+bi+1≥「n2 if i∈J. Note that if iJ∪J′， then bi≥1.

If n=2， by Theorem 5， γ*（Pm[Cn]）=γ*（Pm）=「m+12. Let S={（2i，0）|i=0，1，…，「m+12-1}， it is easy to see that S is a twin dominating set of Pm[C2] and |S|=「m+12.

Next， we consider n≥3. For convenience， we first count the number of bi from i=1 to i=m-2. There are two cases to be considered：

Case 1 bm-2≠0.

Then

∑m-2i=1bi=∑i∈J∪J′bi+∑iJ∪J′bi≥

|J|「n2+m-2-2|J|=m-2+|J|「n2-2|J|≥m-2.

Therefore， ∑m-1i=0bi=b0+bm-1+∑m-2i=1bi≥2「n2+m-2.

Case 2 bm-2=0 （that is |J|≥1）. We consider the following two subcases：

Subcase 2.1 |J|=「m-22.

We have bm-2=0， bm-3=「n2，bm-4=0，bm-5=「n2，…， it follows that bm-i=0 if i is even； bm-i=「n2 if i is old. Thus ∑m-2i=1bi=m-22「n2.

Hence

∑m-1i=0bi≥「n2+「n2+m-22「n2=「m+12「n2.

Subcase 2.2 1≤|J|

It follows that there must exist some even integer j such that bm-j≠0. Then

∑m-2i=1bi=bm-2+bm-3+…+bm-（j-1）+bm-j+…+b1=

0+「n2+…+0+「n2+∑m-ji=1bi≥

j-22「n2+（|J|-j-22）「n2+m-2-（j-2）-2（|J|-j-22）=

j-22「n2+|J|「n2-j-22「n2+m-2-j+2-2|J|+2J-22=

m-2+|J|「n2-2|J|≥m-2.

Thus ∑m-1i=0bi=b0+bm-1+∑m-2i=1bi≥2「n2+m-2.

From above all， we conclude that γ*（Pm[Cn]）≥min{「m+12「n2，2「n2+m-2}. Set

S1={（s，2t）|s∈{0，m-1}，t∈{0，1，…，「n2-1}}，

S2={（2i，2j）|{1，2，…，m-22}，j∈{0，1，…，「n2-1}}，

S3={（i，0）|i∈{1，2，…，m-2}}.

Where S1=2「n2，S2=m-22「n2，S3=m-2.

When 2≤n≤4 or m=3， it is clear that 「m+12「n2≤2「n2+m-2， then |S|=∑m-1i=0bi≥「m+12「n2.

Note that S1∪S3 is a twin dominating set of Pm[Cn] and |S1∪S2|=「m+12「n2. If n≥5 or m≠3，「m+12「n2≥2「n2+m-2， then |S|=∑m-1i=0bi≥2「n2+m-2. Note that S1∪S2 is a twin dominating set of Pm[Cn] and |S1∪S3|=2「n2+m-2.

The following Corollary is obtained from Theorem 6.

Corollary 1 Let m，n≥2， then

γ*（Pm[Pn]）=

「m+12「n2， if m=3 and n is odd， or n=3；

「2m+23，if m≠3 and n=2；

2「n2+m-2，otherwise.

Proof The framework and main idea for this proof are the same as that of Theorem 6. The point to be mode here is that for the case m≠3， one should consider four subcases. n=2，3，4 and n≥5. Hence， the proof is left for the readers.

References：

[1] ARAKI T. The ktuple twin domination in de Bruijin and Kautz digraphs [J]. Disc Math， 2008，308（24）：64066413.

[2] ARAKI T. Connected ktuple twin domination in de Bruijin and Kautz digraphs [J].Disc Math， 2009，309（21）：62296234.

[3] ARUMUGAM S， EBADI K， SATHIKALA L. Twin domination and twin irredundance in digraphs [J]. Appl Anal Disc Math， 2013，7：275284.