有向图字典式积的控制数

马红霞,　刘　娟

(新疆师范大学 数学科学学院，新疆 乌鲁木齐 830017)



有向图字典式积的控制数

马红霞,刘娟*

(新疆师范大学 数学科学学院，新疆 乌鲁木齐 830017)

摘 要：令γ(D)表示有向图D的控制数并且令Dm[Dn] 表示Dm和Dn的字典式积, 其中有向图的点数为m,n≥2。 文章首先给出任意两个有向图字典式积Dm[Dn]的控制数的下界, 并且决定了有向图Km[Dn]; Cm[Dn];Pm[Dn]的控制数。

关键词：控制数;字典式积; 有向图.

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), ND+(v) and ND-(v)denote the sets of out-neighbors and in-neighbors, respectively, of v， dD+(v)=|ND+(v)|and dD-(v)=|ND-(v)| denote the out-degree and in-degree of v in D, respectively. A digraph D is r-regular if dD+(v)=dD-(v)=r for any vertex v in D. Given two vertices u and v in D, we say that u out-dominates v if u=v or uv∈A(D), and v in-dominates u if u=v or uv∈A(D). Let ND+[v]=ND+(v)∪{v} . A vertex v out-dominates all vertices in ND+[v]. A set S∈V(D) is an dominating set of D if S out-dominates all vertices in V(D). The domination number of D, denoted by γ(D), is the minimum cardinality of an dominating set of D.

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)={x0,x1,…,xn-1}and disjoint arc sets A(Dm)and A(Dn), respectively. The lexicographic product Dm[Dn] of Dmand Dnhas vertex set V(Dm)×V(Dn)={(xi,yj)|xi∈V(Dm),yj∈V(Dn)} 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).

In recent years, the domination number of the Cartesian product and strong product of directed cycles and paths has been discussed in [4, 5, 6, 7, 8, 10]. And some results of twin domination in digraphs have been studied in [1, 2, 3, 9]. However, to date no research about domination number has been done for lexicographic product of digraphs. In this paper, we study the domination number of Dm[Dn]. First we give the lower bound of the domination number of Dm[Dn], and then determine the exact values of the domination number of digraphs: Km[Dn];Cm[Dn] ;Pm[Dn].

1Main results

First, we prove that the lower bound of the domination number of Dm[Dn].

Lemma 1.1 For any m,n≥2 , then γ(Dm[Dn])≥γ(Dm).

Let Kmbe complete digraph with every pair of distinct vertices in Kmare adjacent. Clearly, γ(Km)=1. The following theorem is easy to obtain.

Theorem 1.2γ(Km[Dn])=1.

We emphasize that vertices of a directed cycle Cmare always denoted by the integers {0,1,…,m-1}, considered modulo m, throughout this paper. There is an arc xy from x to y in Cmif and only if y≡x+1(modm).

Theorem 1.3For m,n≥2, we have

Proof. Now we consider two cases.

Case 1: γ(Dn)=1.

Case 2: γ(Dn)≥2.

We find that S2={(j,y0)|j∈{0,1,…,m-1}}is a dominating set of Cm[Dn], and |S2|=m, where y0is a dominating set of Dn. Therefore, γ(Cm[Dn])=m.The proof is completed.

Let Pmbe a directed path with vertex set {0,1,…,m-1} throughout this paper. This notation make it convenient to the proof of the following results.

Theorem 1.4Let m,n≥2, then

Case 1: γ(Dn)=1.

Case 2: γ(Dn)≥2.

Subcase 2.1: bm-1=0.

Subcase 2.2: bm-1≠0.

The proof is completed.

参考文献：

[1] T.Araki. The k-tuple twin domination in de Bruijin and Kautz digraphs[J]. Discrete. Math, 2008,(308):6406-6413.

[2] S.Arumugam, K.Ebadi, et al. Twin domination and twin irredundance in digraphs[J]. Discrete. Math, 2013,(7):275-284.

[3] G. Chartrand, P. Dankelmann, M. Schultz, H.C.Swart. Twin domination in digraphs[J]. Ars Combinatoria. 2003,(67):105-114.

[4] J. Liu, X.D. Zhang, X. Chen, J. Meng. The domination number of Cartesian products of directed cycles[J]. Inform. Process. Lett, 2010,110(5):171-173.

[5] J. Liu, X.D. Zhang, J. Meng. On domination number of Cartesian product of directed path[J]. Comb. Optim. 2011,22(4):651-662.

[6] M. Mollard. On the domination of Cartesian product of directed cycles: Results for certain equivalence classes of lengths[J]. Discuss. Math. Graph Theory, 2013,33(2):387-394.

[7] M. Mollard. The domination number of Cartesian product of two directed paths[J]. Comb. Optim, 2014,(27):144-151.

[8] R. S. Shaheen. Domination number of toroidal grid digraphs[J]. Utilitas Math, 2009,(78):175-184.

[9] Y.L. Wang. Efficient twin domination in generalized de Bruijn digraphs[J]. Discrete Math, 2015,(338):36-40.

[10] X.D. Zhang, J. Liu, X. Chen, J.Meng. On domination number of Cartesian product of directed cycles[J]. Inform. Process. Lett, 2010,111(1):36-39.

The Domination Number of Lexicographic Product of Digraphs

MA Hong-xia, LIU Juan*

(CollegeofMathematicsSciences,XinjiangNormalUniversity,Urumqi,Xinjiang, 830017,China)

Abstract:Let γ(D)denote the domination number of digraph D and let Dm[Dn] denote the lexicographic product of Dm and Dn, digraphs of order m,n≥2. In this paper, we first give the lower bound of the domination number of Dm[Dn], and then determine the exact values of the domination number of digraphs: Km[Dn] ;Cm[Dn] ;Pm[Dn].

Key words:Domination number; Lexicographic product; Digraphs

中图分类号:O157.5

文献标识码：A

文章编号：1008-9659(2016)01-049-04

*[通讯作者]刘娟(1981-)，女，安徽阜阳人，博士，教授，主要从事图论及其应用研究。

[作者简介]马红霞(1990-)，女，新疆乌鲁木齐人，硕士研究生，主要从事图论及其应用研究。

[基金项目]国家自然科学基金项目(61363020);国家自然科学基金项目(11301450);中国国家留学基金资助；新疆维吾尔自治区青年科技创新人才培养工程(2013731011)。

[收稿日期]2015-11-13