• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    The Twin Domination Number of Cartesian Product of Directed Cycle and Path

    2020-07-08 03:25:34MaHongxia

    Ma Hongxia

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

    Abstract Let γ*(D)denote the twin domination number of digraph D and let Cm□Pn denote the Cartesian product of the directed cycle Cm and the directed path Pn, for m,n≥2. In this paper, we give a lower bound for γ*(Cm□Pn). Furthermore, we determine the exact values: γ*(C2□Pn)=n; γ*(C3□Pn)=n+2; γ*(C4□ γ*(C5□Pn)=2n+2.

    Key words Twin domination number Cartesian product Directed cycle Directed path

    1 Introduction

    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.

    In this paper, we study the twin domination number ofCm□Pnand obtain the lower bound ofγ*(Cm□Pn).Furthermore, we determine the exact values ofγ*(Cm□Pn), whenm=2,3,4,5.

    2 Main results

    We emphasize that the vertices of a directed cycleCmare always denoted by the integers {0,1,…,m-1} and the vertices of a directed pathsPnare denoted by the integers {0,1,…,n-1}.These notations turned out to be convenient to formulate the proof of the following results.

    Letm=3k+1 andai≤k, thenai+ai+1≥2k+1.Whenai≥k+1, it is obvious thatai+ai+1≥2k+1 holds.Hence, whenm≡1(mod 3),ai+ai+1≥2k+1.

    Letm=3k+2 andai≤k, thenai+ai+1≥2k+2.Whenai≥k+1, it is easy to see thatai+ai+1≥2k+2.Thus, we haveai+ai+1≥2k+2 form≡2(mod 3).

    ProofLetSbe a twin dominating set ofCm□Pnwithn≥4.We apply the following algorithm:I=?,J=?,i=1;

    Whilei≤n-3 do

    ifai≥k+1 then

    I=I∪{i};i=i+1

    else

    J=J∪{i,i+1};i=i+2

    end if

    end while.

    From the above algorithm, we see that wheni=n-1 ori=n-2, the algorithm will stop.Hence we get two disjoint setsI,Jsuch that either {0,1,…,n-1}={0}∪I∪J∪{n-1} or {0,1,…,n-1}={0}∪I∪J∪{n-2,n-1}.

    Therefore, we have

    (1)

    or

    (2)

    We consider the following three cases.

    Case 1m≡0(mod 3).

    Subcase 1.11∈I.

    In the second case we get

    Subcase 1.21?I.

    Thusa1≤k.So we obtain thata0≥2kby Lemma 2.1.Then by(1)

    According to(2), we get that

    |S|≥2k+|I|(k+1)+(n-3-|I|)k+3k

    Case 2m≡1(mod 3).

    Similarly, if 1∈I, then

    Otherwise

    If 1?I, we can obtain thata0≥2k+1 by Lemma 2.1.Thus,

    Case 3m≡2(mod 3).

    We now investigate the twin domination number ofC2□Pn.

    It is clear thatγ*(C2□P2)=2 andγ*(C2□P3)=3.Whenn≥4, by Theorem 2.3, we haveγ*(C2□Pn)≥n.We define a setS1={(0,j)|j∈{0,1,…,n-1}}.It is easy to see thatS1is a twin dominating set ofC2□Pnand |S1|=n.Therefore we obtain the following Theorem.

    Theorem 2.4Letn≥2, thenγ*(C2□Pn)=n.

    We now consider the twin domination number of Cartesian productC3□Pnand define a setS2(see Figure 1)as:S2={(0,0),(2,0);(0,j)j≡0(mod 3);(1,j)j≡1(mod 3);(2,j)j≡2(mod 3), forj≥1}.Note that |S2|=n+1.

    Figure 1 The set S2

    Theorem 2.5Letn≥2, thenγ*(C3□Pn)=n+2.

    ProofIt is easy to calculate thatγ*(C3□P2)=4 andγ*(C3□P3)=5.Letn≥4, by Theorem 2.3, we getγ*(C3□Pn)≥n+2.

    Note thatS2∪{(0,n-1)} is a twin dominating set ofC3□Pn, whenn≡0,2(mod 3).Similarly,S2∪{(2,n-1)} is a twin dominating set ofC3□Pn, whenn≡1(mod 3).Thusγ*(C3□Pn)=n+2.

    Figure 2 The set S3

    We consider the twin domination number of Cartesian productC5□Pn, and define a setS4(see Figure 3)as:S4={(0,0),(2,0),(4,0),(0,j),(2,j)j≡0(mod 3);(1,j),(3,j)j≡1(mod 3);(2,j),(4,j)j≡2(mod 3), forj≥1}.Note that |S4|=2n+1.

    Figure 3 The set S4

    It is easy to see thatγ*(C5□P2)=6 andγ*(C5□P3)=8.Whenn≥4, we obtain thatγ*(C5□Pn)≥2n+2 by Theorem 2.3.

    Note thatS4∪{(4,n-1)} is a twin dominating set ofC5□Pn, whenn≡1,2(mod 3).Similarly,S4∪{(0,n-1)} is a twin dominating set ofC5□Pn, whenn≡0(mod 3).Therefore we can obtain the following Theorem.

    Theorem 2.7Letn≥2, thenγ*(C5□Pn)=2n+2.

    富源县| 阳江市| 库车县| 色达县| 余江县| 和田市| 达日县| 平潭县| 乐业县| 榕江县| 杨浦区| 正阳县| 信阳市| 尉犁县| 乐陵市| 东安县| 香河县| 通州市| 文昌市| 横峰县| 靖安县| 凤阳县| 陈巴尔虎旗| 安平县| 澎湖县| 大庆市| 清徐县| 和政县| 含山县| 木里| 方山县| 观塘区| 平塘县| 锡林浩特市| 云和县| 抚松县| 凯里市| 贞丰县| 毕节市| 濮阳市| 剑川县|