路與圈笛卡爾乘積圖的誤報(bào)容錯(cuò)支配數(shù)

李紅麗，趙承業(yè)

(中國(guó)計(jì)量大學(xué) 理學(xué)院，浙江 杭州 310018)

圖的誤報(bào)容錯(cuò)支配集可以在監(jiān)測(cè)節(jié)點(diǎn)發(fā)出錯(cuò)誤信息的時(shí)候仍然能夠定位事故發(fā)生節(jié)點(diǎn)，并識(shí)別發(fā)出錯(cuò)誤信息的節(jié)點(diǎn)，因此在網(wǎng)絡(luò)容錯(cuò)設(shè)計(jì)中具有很重要的價(jià)值[3-5].

關(guān)于圖的誤報(bào)容錯(cuò)支配數(shù)已經(jīng)有了很多結(jié)論[6-9],2009年,Slater[2]引入了誤報(bào)容錯(cuò)支配的概念并且給出了誤報(bào)容錯(cuò)支配數(shù)的一個(gè)下界,即如果對(duì)于一個(gè)圖G(頂點(diǎn)數(shù)n=|V(G)|)它的最大度ΔG=r,特別的,如果圖G是r正則圖,則它的最小誤報(bào)容錯(cuò)支配數(shù)γLR(G)≥(6/(3r+2))n.2012年王浩麗[10]給出了廣義Petersen圖P(n,1),P(n,2)的誤報(bào)容錯(cuò)支配數(shù)的值.2013年,裴利丹[11]等確定了γ(Pm×Cn)的值.其中m=3,4.目前針對(duì)路與圈笛卡爾乘積圖誤報(bào)容錯(cuò)支配還沒有研究,本文主要討論P(yáng)m×Cn(m=3,4)的誤報(bào)容錯(cuò)支配數(shù).

1　引理及主要結(jié)果

首先給出幾個(gè)記號(hào).

在圖Pm×Cn中,令V′(i,t)={v0(i+j),v1(i+j),…,v(m-1)(i+j)：0≤j≤t}是Pm×Cn的一個(gè)子集,其中0≤i≤n-1且0≤t≤n.顯然,

令L是Pm×Cn中任意一個(gè)誤報(bào)容錯(cuò)支配集,且令ni,t代表頂點(diǎn)子集V′(i,t)∩L中的頂點(diǎn)數(shù)目,即ni,t=|V′(i,t)∩L|.

引理1當(dāng)n≥5時(shí),

γLR(P3×Cn)≤.

證明:要證明該引理，只需找出一個(gè)滿足該引理?xiàng)l件的誤報(bào)容錯(cuò)支配集L.

當(dāng)n=5時(shí),令

L={v10,v01,v11,v21,v03,v13,v23,v14}.

當(dāng)n=6時(shí),令

L={v01,v11,v21,v03,v13,v23,v05,v15,v25}.

當(dāng)n≥6時(shí),令

S={v0(2i+1),v1(2i+1),v2(2i+1)：0≤i≤k-1}

且

(1)

不難驗(yàn)證L是圖P3×Cn的滿足引理?xiàng)l件的誤報(bào)容錯(cuò)支配集.

由于P3×Cn中每個(gè)頂點(diǎn)必須被支配兩次，因此以下觀察成立.即

觀察1對(duì)任意i∈{0,1,…,n-1},

ni,1≥2.

引理2對(duì)任意i∈{0,1,…,n-1},有ni,2≥3,如果存在一整數(shù)l∈{0,1,…,n-1},滿足nl,2=3,則{v0(l+1),v1(l+1),v2(l+1)}?L且nl+1,2=6.

證明:由觀察1容易得出對(duì)任意i∈{0,1,…,n-1}有ni,2≥3.現(xiàn)假設(shè)存在一個(gè)整數(shù)l∈{0,1,…,n-1},使得nl,2=3,由觀察1,我們考慮以下兩種情形:

情形1nl,1=2,nl+2,0=1.

為支配V′(l,2)中每個(gè)頂點(diǎn)兩次,我們分以下兩種情形考慮:

1)nl,0=0,nl+1,0=2,nl+2,0=1時(shí),V′(l,0)中存在一個(gè)頂點(diǎn)至多被支配一次,這與每個(gè)頂點(diǎn)必須被支配兩次矛盾,因此此情形不成立.

2)nl,0=nl+1,0=nl+2,0=1時(shí),V′(l+1,0)中至少存在一點(diǎn)至多被支配一次，矛盾.

情形2nl,1=3,nl+2,0=0.

為支配V′(l,2)中每個(gè)頂點(diǎn)兩次,考慮兩種情形:

1)nl,0=1,nl+1,0=2,nl+2,0=0時(shí),V′(l+2，0)中存在一點(diǎn)至多被支配一次，矛盾.

2)nl,0=0,nl+1,0=3,nl+2,0=0時(shí),{v0(l+1),v1(l+1),v2(l+1)}?L,則V′(l+1,0)中的每一個(gè)頂點(diǎn)被支配兩次,且對(duì)任意的一對(duì)u,v∈V′(l+1,0),|(N[u]∪N[v])∩L|=3成立.又由于{v0(l+2),v1(l+2),v2(l+2)}?L,為支配V′(l+2,0)中每個(gè)頂點(diǎn)兩次,{v0(l+3),v1(l+3),v2(l+3)}?L.則nl+1,2=6成立,且在V′(l+2,0)滿足對(duì)任意一對(duì)頂點(diǎn)u,v∈V′(l+2,0),|(N[u]∪N[v])∩L|≥3.

引理3對(duì)任意n≥5，

γLR(P3×Cn)≥.

證明:我們考慮以下兩種情況:

通過情形1和情形2,證得引理3.

根據(jù)引理1和引理3,得到如下定理:

定理1對(duì)任意的n≥5,有

γLR(P3×Cn)=.

引理4對(duì)任意n≥5,

證明:要證明該引理,只需給出一個(gè)滿足該引理?xiàng)l件的誤報(bào)容錯(cuò)支配集L.

當(dāng)n=5時(shí),令

L={v00,v30,v01,v11,v21,v31,v03,v13,v23,v33,v24}.

當(dāng)n=6時(shí),令

L={v01,v11,v21,v31,v03,v13,v23,v33,v05,v15,v25,v35}.

當(dāng)n≥6時(shí),令

S={v0(2i+1),v1(2i+1),v2(2i+1),v3(2i+1)：0≤i≤k-1}

且

(2)

不難驗(yàn)證L是圖P4×Cn的滿足引理?xiàng)l件的誤報(bào)容錯(cuò)支配集.

觀察2對(duì)任意i∈{0,1,…,n-1},

ni,1≥3.

引理5對(duì)任意i∈{0,1,…,n-1},有ni,2≥4.如果存在一個(gè)整數(shù)l∈{0,1,…,n-1},滿足nl,2=4,則{v0(l+1),v1(l+1),v2(l+1),v3(l+1)}?L,nl+1,2=8.

證明:由觀察2不難得出i∈{0,1,…,n-1},使得ni,2≥4.現(xiàn)假設(shè)存在一個(gè)整數(shù)l,滿足nl,2=4,對(duì)任意l∈{0,1,…,n-1}.由觀察2,我們考慮以下兩種情況:

情形1nl,1=3,nl+2,0=1.

為支配V′(l,2)中每個(gè)頂點(diǎn)兩次,我們分以下兩種情形考慮:

1)nl,0=1,nl+1,0=2,nl+2,0=1時(shí),V′(l，0)和V′(l+2,0)中存在一個(gè)頂點(diǎn)至多被支配一次,這與每個(gè)頂點(diǎn)必須被支配兩次矛盾,因此此情形不成立.

2)nl,0=0,nl+1,0=3,nl+2,0=1時(shí),則V′(l,0)中存在一個(gè)頂點(diǎn)至多被支配一次,矛盾.

情形2nl,1=4,nl+2,0=0.

為支配V′(l,2)中每個(gè)頂點(diǎn)兩次,分以下兩種情形考慮:

1)nl,0=1,nl+1,0=3,nl+2,0=0時(shí),V′(l+2,0)中存在一個(gè)頂點(diǎn)至多被支配一次，矛盾.

2)nl,0=0,nl+1,0=4,nl+2,0=0時(shí),{v0(l+1),v1(l+1),v2(l+1),v3(l+1)}?L,則V′(l+1,0)中的每一個(gè)頂點(diǎn)都被支配兩次,且對(duì)任意的一對(duì)頂點(diǎn)u,v∈V′(l+1,0),|(N[u]∪N[v])∩L|≥3成立.又由于{v0(l+2),v1(l+2),v2(l+2),v3(l+2)}?L為支配V′(l+2,0)中每個(gè)頂點(diǎn)兩次,{v0(l+3),v1(l+3),v2(l+3),v3(l+3)}?L.則nl+1,2=8成立,且對(duì)任意的一對(duì)頂點(diǎn)u,v∈V′(l+2,0),|(N[u]∪N[v])∩L|≥3.

引理6對(duì)任意n≥5,有

證明:考慮以下兩種情形:

情形1當(dāng)n為偶數(shù)時(shí),由引理5,假設(shè)ni,2=4,對(duì)任意的i∈{0,1,…,n-1},則有{v0(i+1),v1(i+1),v2(i+1),v3(i+1)}?L,ni+1,2=8.由圖的對(duì)稱性,圖P4×Cn的誤報(bào)容錯(cuò)支配集的頂點(diǎn)數(shù)至少為2n,即γLR(P4×Cn)≥2n.

情形2當(dāng)n為奇數(shù)時(shí),如同情形1,假設(shè)ni,2=4,對(duì)任意的i∈{0,1,…,n-1},則有{v0(i+1),v1(i+1),v2(i+1),v3(i+1)}?L,ni+1,2=8.由對(duì)稱性,可知{v0(i+3),v1(i+3),v2(i+3),v3(i+3)}?L,{v0(i+5),v1(i+5),v2(i+5),v3(i+5)}?L，等依次類推.因?yàn)閚為奇數(shù),由圖的性質(zhì),存在一個(gè)整數(shù)l,使得nl,1=0對(duì)任意的l∈{0,1,…,n-1},為使V′(l,1)中的每一個(gè)頂點(diǎn)被L支配兩次,由觀察1,nl,1≥3.綜上,當(dāng)n為奇數(shù)時(shí)圖P4×Cn的誤報(bào)容錯(cuò)支配集的頂點(diǎn)數(shù)至少為2n+1,即γLR(P4×Cn)≥2n+1.

通過情形1和情形2,證得引理6.

根據(jù)引理4和引理6,得到如下定理:

定理2對(duì)任意的n≥5,有

2　m大于4的猜想

通過觀察圖Pm×Cn(m=3,4)的誤報(bào)容錯(cuò)支配數(shù)的精確值，我們可以發(fā)現(xiàn)它和m,n的關(guān)系大致滿足.對(duì)m大于4的情形,我們猜想存

在非負(fù)整數(shù)c,d,對(duì)任意的m,n有下面的結(jié)論成立:

+d.

【參考文獻(xiàn)】

[1]HARAY F, HAYNES T W. Double domination in graphs[J].ArsCombin, 2000,55:201-213.

[2]SLATER P J. Liar’s domination[J].Network, 2009,54(2):70-74.

[3]RODEN, MIRANDA L, SLATER, et al. Liar’s domination in graphs[J].DiscreteMathematics, 2009,309(19):5884-5890.

[4]ALIMADADI A, CHELLALI M, MOJDEH D A. Liar's dominating sets in graphs[J].DiscreteAppliedMathematics, 2016,211:204-210.

[5]張超,趙承業(yè).計(jì)算樹的[1,2]-數(shù)的算法研究[J].中國(guó)計(jì)量學(xué)院學(xué)報(bào),2015,26(2):243-246.

ZHANG C, ZHAO C Y. Research on the algorithms of computing the[1,2]-number of trees[J].JournalofChinaUniversityofMetrology,2015,26(2):243-246.

[6]ALIMADADI A, MOJDEH D A, RAD N J. Various bounds for liar’s domination number[J].DiscussionesMathematicaeGraphTheory,2016,36(3):629-641.

[7]PANDA B S, PAUL S. Liar’s domination in graphs: Complexity and algorithm[J].DiscreteAppliedMathematics, 2013,161:1085-1092.

[8]PANDA B S, PAUL S. A linear time algorithm for liar’s domination problem in proper interval graphs[J].InformationProcessingLetters, 2013,113:815-822.

[9]PANDA B S, PAUL S, PRADHAN D. Hardness results, approximation and exact algorithms for liar's domination problem in graphs[J].TheoreticalComputerScience,2015,573:26-42.

[10]王浩麗.圖的支配數(shù)及兩個(gè)相關(guān)問題的研究[D].大連：大連理工大學(xué),2011.

WANG H L.ResearchonDominationNumberandTwoRelatedProblemsofGraphs[D].Dalian: Dalian University of Technology,2011.

[11]裴利丹,連小娟,潘向峰.路與圈的笛卡爾乘積的控制數(shù)[J].合肥學(xué)院學(xué)報(bào)(自然科學(xué)版),2013,23(3):24-28.

PEI L D,LIAN X J,PAN X F.On the domination number of the cartesian products of the cycle and the path[J].JournalofHefeiUniversity(NaturalSciences),2013,23(3):24-28.