关于网络的控制数的几点注记.pdf

DOI:10.159606093.2023.03.016Vol.27No.3Operations Research TransactionsSep.,2023第2 7 卷第3 期2023年9 月运筹学学报关于网络的控制数的几点注记郝建修1,摘要(d,w)-控制数是一个度量共享网络资源的可靠性的重要参数。（1,1)-控制数就是图论中的经典控制数，(d,w)-控制数是(1,1)-控制数的一个直接推广。本文给出了计算(1,w)-控制数的一个下界方法和一个上界方法。应用这两个方法，求出了超立方体的(1,n一1)-控制数和(1,n)-控制数，求出了4基n立方体的(1,2 n一1)-控制数和(1,2 n)-控制数，求出了n维折叠超立方体的(1,n)-控制数。关键词（d,w)-控制数，超立方体，网络，组合问题中图分类号0 157.52010数学分类号0 5C20Some remarks about dominating number of networkHAO Jianxiul,tAbstract(d,w)-dominating number is an important measuring parameter for thereliability of sharing common source in a network.(1,1)-dominating number is also knownas dominating number which is a classical parameter in graph theory.(d,w)-dominatingnumber is a simple generalization of(1,1)-dominating number.In this paper we present alower bound and an upper bound for the calculating of(1,w)-dominating number.Usingthese two bounds,we find the(1,n-1)-dominating number and(1,n)-dominating numberfor hypercube,we find the(1,2n-1)-dominating number and(1,2n)-dominating numberfor 4-ary n-cube,and the(1,n)-dominating number for n dimensional folded hypercube.Keywords(d,w)-dominating number,hypercube,network,combinatorial problemChinese Library Classification O157.52010 Mathematics Subject Classification 05C20图论提供一个描述互联网络的自然方法，每个顶点对应一个处理器或一个转换元素，每条边对应一个通信线路。在一个网络中，我们用(d,w)-控制数去度量分享公共资源的可信度。设G是一个w连通网络，S是G的一个(d,w)-控制集。设G的每一个顶点代表一个计算机，如果把公共资源放在S的每个顶点上，在V(G)S中的每个顶点都能通过w条内部不相交的路（每条路长至多为d）来分享这些公共资源。考虑到安全性，我们想让S中的计算机的数目尽可能地小 1。本文只研究简单连通图。收稿日期：2 0 19-0 5-131浙江师范大学数学与计算机学院，浙江金华3 2 10 0 4；Institute of Mathematics and ComputerSciences,Zhejiang Normal University,Jinhua 321004,Zhejiang,Chinat通信作者E-mail:18627卷郝建修1预备知识定义1)设G是一个w（w 1）连通图，S是V(G)的一个非空真子集，yEV(GS。从y到S中某顶点的路称为(y,S)路。w条内点不交(y,S)路集记为Pu(G;y,S),Pw(G;y,S)中路的最大长度称为Pw(G;y,S)的长。对任何给定的整数d(d1)，如果存在长度至多为d的(y,S)路集Pw(G;y,S)，那么称S能(d,w)-控制y。如果S能(d,w)-控制G一S中的每个顶点,那么称S为G的(d,w)-控制集。用记号Ld,w(G)表示G的所有(d,w)-控制集的族。参数rd,w(G)=min(ISIIS e Ld,w(G)称为G的(d,w)-控制数。G的(d,w)-控制集S称为最小的，如果|S|=rdw(G)。引理1 1设G是一个w连通图，w和d都是正整数，那么(1)1假设r2,2(G)存在，则r2,2(G)a(G),这里a(G)表示G的独立数，见定义4。(2)如果G是w+1连通图,rd,w(G)rdw+1(G)。(3)如果H是G的一个w连通支撑子图,rd,w(G)rd,w(H)。(4)rd+1,w(G)rd,w(G)。定义2 定义超立方体Qn如下：V(Qn）=a 12an|ciE0,1,i=1,2,n。设=2 12 2 n,y=12 n（a,)是Qn的一条边当且仅当|a11|+|z2-2l+.+an-ynl=1。引理2 1Qn的连通度是n，独立数是2 n-1。定义3 2 设k2，n 1，k 和n都是整数，定义k基n立方体Qh如下：有kn个顶点，每个顶点有如下形式：=ann-11，a(0,1,k-1),1in。两个顶点=nn-1和y=Unn-1相邻，当且仅当存在一个整数j，1n，使得aj=yj1(modk)，并且at=t 对所有tE1,2,n)-)都成立。引理3 2 Qh的连通度是2 n，k 3。定义4lI我们定义n维折叠超立方体FQn如下：V(FQn）=V(Qn)。设a=122Ln，y=yiy y1,(a,y)是一条补边当且仅当ai=1-yi,i=1,2,n。E(F Q n)=E(Q n)U(c,y)(a,)是一条补边),n1。引理4l1FQn的连通度是n+1。定义5 3】设S是V(G)的一个子集，如果S中的任何两个顶点在G中都不相邻，我们就称S是G的独立集。如果G中没有独立集R使得|RIISI，我们就称S是G的最大独立集。称G的最大独立集的顶点数为G的独立数，用a(G)表示。设K是V(G)的一个子集，如果G的每条边至少有一个端点在K中，我们就称K是G的一个覆盖。G的最小覆盖的顶点数称为G的覆盖数，用b6(G)表示。引理5 3 a(G)+b(G)=V(G)。引理6 4 a(FQn)2n-1,n 3。2主要结果定理1如果G是一个w连通图，w1,d2,那么rd,w(G)a(G)。证明设S是G的一个顶点独立集，且|S|=(G)。显然，ISI1。断言1对任意yEV(G)-S,存在一个w内部不相交的(y,S)-路集。1873期关于网络的控制数的几点注记事实上，设ES,由著名的Mengers定理，和y被w条内部不相交的路 Pi,P2，Pu 连接。当我们沿着P路从y到a前进时，设s是使得sES的第一个顶点，i=1,2,，W。用这种方式我们获得一个(y,S)-路集，断言1证毕。如果(y,S)-路集不唯一，设Pw(G;y,S）是内部不相交(y,S)-路集，使得其中的最长路的长尽可能小。设Pw(G;y,S)=Q1,Q2,*,Qw),d(Q1)d(Q2).d(Qw),d(Qi)表示Q;的边数,i=1,2,W。断言2 d(Qw)2。反证法。假设d(Qw)2。设Q=y2122ztz,t=d(Qw）1,t 2,S,则对于任意uE S,不存在(u,zt-1)E E(G)。否则，设Q=yz1z2zt-1u,那么d(Q）d(Q w)。当d(Qw-1)(G)，这是一个矛盾。由引理1(4)，本定理成立。注：由引理1(2)，当w2，我们可能加强了引理1(1)。当w等于图G的连通度，有可能r2,w(G)k，i =1,2,r。设G是w连通图,G1,G2，G r 是G的诱导子图,V(Gi)nV(Gj)是一个空集，V(G)=V(G1)UV(G2)U.UV(Gr)。如果G;是w-k,连通的,这里ki=max(tlu与V(G)-V(G)中的t个顶点相邻,uEV(Gi),i=1,2,.,r,那么T1,w(G)r1,w-hi(Gi)+r1,w-k2(G2)+.+r1,w-kr(Gr)。进一步，设G；是w连通的。如果r1,=1,2,r，那么r1,w(G)=r1,w(G1)+r1,ww(G2)+.+r1,w(Gr)。证明(1)反证法。假设r1,w(G)ki，所以S,不是一个空集,i=1,2,.,r。18827卷郝建修断言1存在jE1,2,，r,使得在G,中,如果S,能(1,pj)-控制Gj-S，则piw-kj。否则，若对于任意i，均有piW一ki，那么S;l r1,w-k;(Gi),i=1,2,.,r。因此，ISIT1,u.:+T1.3-k,(Gt),与假设矛盾，断言1证毕。因为对于任意顶点uEV(G;）-Si，最多与V(G)-V(G,)中kj个顶点相邻，所以S能(1,Pi+ki)-控制Gj-S，但pi+kj1。设Qw=y212ztz,t=d(Q）-1,ES。可是,边(y,z1)不被S覆盖，这是一个矛盾，断言2 成立。由定义1，本定理成立。注：正如定理5 7 所示，定理3 和4提供了两个计算著名网络的(1,w)-控制数的一般方法。当w等于G的连通度，rl.w(G)b(G)有可能成立。例如，设V(G)=U1,V2,V3,U4,V5,V6),E(G)=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V6),(V6,V1),(V2,V4),(V3,V5)定理5 r1,n-1(Qn)=r1,n(Qn)=2n-1,n 2。证明用数学归纳法。首先，令n=2，定理显然成立。其次，假设n=k时定理成立，即r1,k-1(Qk）=r 1,k(Qk）=2 k-1。以下令n=k+1。我们把Qk+1分解为两个k维超立方体，由定理3(2)可知T1,(Qk+1)=1,k-1(Qk)+r1,k-1(Qk)=2k。因此,1,n-1(Qn)=2n-1 成立。由引理1(2)可知T1,n(Qn)r1,n-1(Qn)=2n-1。189关于网络的控制数的几点注记3期由引理2 和引理5可知b(Q=2n-1。由定理4可知r1,n(Qn)2n-1,定理证毕。注：在文献 5中，r1,n(Qn)=2n-1已用不同方法获得。定理6 如果G是Q,那么r1,2n-1(G)=r1,2n(G)=22n-1。证明用数学归纳法。首先，令n=1,则Q1=C4，定理显然成立。其次，假设n=k时定理成立，即假设r1,2k-1(Q）=T 1,2 k(Q）=0.54成立。以下令n=k+1。我们把V(Q+1,）在Q+1中的诱导子图定义为Q+1,，这里V(Q+1,i)=(ah+17k*21ck+1=1),i=0,1,2,3。我们把Q+1分解为Q+1,0，Q+1,1，Q+1,2，Q+1,3。由定理3(1)可知T1,(+1)-1(Qt+1)11,(+1)-1-2(Q+1,)+T1,(+1)-1-2(Q$+1,1)+T1,2(h+1)-1-2(Q#+1,2)+T1,2(+1)-1-2(Q#+1,3)=0.5 4hk+1由引理1可知综上有r1,2(k+1)(Qh+1)1(Q+1)0.5 4k+1。T1,2n(Qn)r1,2n-1(Q)0.5 4。以下我们递归地为Q构造两个独立集。首先,对Q1,令S1,e=0,2),S1,=V(Q1)-S1,e。其次，对Q，假设Sk，和Sk，。已构造好，对Q+1我们构造Sk+1,和Sh+1,。如下：Sh+1,e=0akak-1.22ilakTk-1.221 E Sk,eU2CkTk-1.2i1|kLk-1.221 E Sk,eU1akak-1.221lkTk-1.2T1 E Sk,oU3ckk-1.22iakTk-.271E Sk,o,Sk+1,o=V(Q+1)-Sk+1,e 由定义3 和定义4可知，Sn,e和Sn.。都是Q的独立集。因此，a(G)22n-1。断言1 a(G)22n-1。与引理6 的证明类似。设I是G的一个独立集，定义G*如下：V(G*)=V(G),E(G*)=(anan-1.20,nan-1.21)E 0,1,2,3,2 inU(anan-1.22,anan-23)a;E 0,1,2,3,2 i n)。显然，InV(G*)/22n-1,断言1成立。(2)如果n是奇数,那么r1,n+1(FQn)19027卷郝建修因此,a(G)=22n-1 成立。由引理5可知b(G)=22n-1。由定理4可知r1,2n(G)22n-1,本定理证毕。定理7 如果2那么定理7 如果G=FQn，n 2,那么(1)r1.n(FQn)=2n-1O证明（1)当n=2,定理显然成立。以下设n3,设G;是顶点集(a1a2n|1a2anEV(FQn),a1=i在FQn中的诱导子图，i=0,1。由定义3,G；是Qn-1。由定理3(1)和定理5可知T1,n(FQn)r1,n-2)+T1,n=2(Qn-1)=2n-1。由引理1(3)和定理5可知T1,n(FQn)r1,n(Qn)=2n-1。综上可知r1,n(FQn)=2n-1。(2）n是奇数。类似地，由定理3(1)和定理5可知r1,n+i(FQn)ri2-1)=2n-1,以下我们为FQn递归地构造两个独立集。首先,对FQ3，令S3,*=001,100,010,111,S3,*=V(FQ3)-S3,*。其次，对FQk，假设Sk和Sk*已构造好。定义S+2,=00a112.122.Tk E Sk,*U 11a122 k122.k E Sk,U 10r12.k1.k E Sh*U 01a122 ka122.k E Sk,*),Sk+2*=V(FQk+2)-Sk,*c由定义3 和4可知Sn*和Sn,*都是FQn的独立集。因此，(G）2 n-1。由引理6 可知a(G)=2n-1,由引理5可知b(G)=2n-1,由定理4可知r1,n+1(G)2n-1。因此,结论(2)成立，本定理证毕。参考文献1 Xu J M.Combinatorial Network Theory M.Beijing:Science Publisher,2007.2 Wang S Y,Li Y,Yang Y X.Fault Tolerant Embeddings in Interconnection Networks M.Beijing:Science Publisher,2012.3 Bondy J A,Murty U S R.Graph Theory with Applications M.London:The Macmillan PressLtd,1976.4 Hsieh S Y,Tsai C Y,Chen C A.Strong diagnosability and conditional diagnosability ofmultiprocessor systems and folded hypercubes J.IEEE Transactions on Computers,2013,62(7):1472-1477.5 Xie X,Xu J M.(d,w)-dominating numbers of hypercube networks J.Journal of MathematicalStudy,2007,2(2):217-222.