李红丽，赵承业

(中国计量大学 理学院，浙江 杭州 310018)

图的误报容错支配集可以在监测节点发出错误信息的时候仍然能够定位事故发生节点，并识别发出错误信息的节点，因此在网络容错设计中具有很重要的价值[3-5].

关于图的误报容错支配数已经有了很多结论[6-9],2009年,Slater[2]引入了误报容错支配的概念并且给出了误报容错支配数的一个下界,即如果对于一个图G(顶点数n=|V(G)|)它的最大度ΔG=r,特别的,如果图G是r正则图,则它的最小误报容错支配数γLR(G)≥(6/(3r+2))n.2012年王浩丽[10]给出了广义Petersen图P(n,1),P(n,2)的误报容错支配数的值.2013年,裴利丹[11]等确定了γ(Pm×Cn)的值.其中m=3,4.目前针对路与圈笛卡尔乘积图误报容错支配还没有研究,本文主要讨论Pm×Cn(m=3,4)的误报容错支配数.

1　引理及主要结果

首先给出几个记号.

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

令L是Pm×Cn中任意一个误报容错支配集,且令ni,t代表顶点子集V′(i,t)∩L中的顶点数目,即ni,t=|V′(i,t)∩L|.

引理1当n≥5时,

γLR(P3×Cn)≤.

证明:要证明该引理，只需找出一个满足该引理条件的误报容错支配集L.

当n=5时,令

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

当n=6时,令

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

当n≥6时,令

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

且

(1)

不难验证L是图P3×Cn的满足引理条件的误报容错支配集.

由于P3×Cn中每个顶点必须被支配两次，因此以下观察成立.即

观察1对任意i∈{0,1,…,n-1},

ni,1≥2.

引理2对任意i∈{0,1,…,n-1},有ni,2≥3,如果存在一整数l∈{0,1,…,n-1},满足nl,2=3,则{v0(l+1),v1(l+1),v2(l+1)}⊂L且nl+1,2=6.

证明:由观察1容易得出对任意i∈{0,1,…,n-1}有ni,2≥3.现假设存在一个整数l∈{0,1,…,n-1},使得nl,2=3,由观察1,我们考虑以下两种情形:

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

为支配V′(l,2)中每个顶点两次,我们分以下两种情形考虑:

1)nl,0=0,nl+1,0=2,nl+2,0=1时,V′(l,0)中存在一个顶点至多被支配一次,这与每个顶点必须被支配两次矛……