完全二部图优美性质探索

把丽娜， 刘 倩， 刘信生， 姚 兵

( 西北师范大学 数学与统计学院， 甘肃 兰州 730070 )

完全二部图优美性质探索

把丽娜， 刘 倩， 刘信生， 姚 兵*

( 西北师范大学 数学与统计学院， 甘肃 兰州 730070 )

图论的二部图及其标号在实际应用中较多，尤其最近图标号被应用于新型的图形密码设计．首先构造出了组合完全二部图与串联完全二部图，发现了一种叫做奇边魔幻全标号的标号，并给出了组合完全二部图具有奇边魔幻全标号的证明．此外，得出了串联完全二部图是优美图、(k，d)-优美图的结论．

树；完全二部图；优美标号；(k，d)-优美标号

0 引 言

图的标号设计是图论中具有实际应用背景的研究课题．在图论的研究中，图的第一个标号问题是在20世纪60年代由Ringel[1]提出的，人们根据应用的需要发现了许多关于简单图的标号和猜想．优美图是图的标号理论中十分重要的课题之一．1966年，Rosa在其关于图同构分解问题的研究中提出了关于优美树的猜想，认为“所有的树图都是优美的”[2]．猜想的提出引起了图论研究者的广泛关注，使得包括优美标号、奇优美标号在内的图标号问题研究得到了空前的发展．图的优美标号问题是组合数学研究专题，它不仅属于图论的领域而且在设计理论的范畴．优美图在物流运输、编码理论、雷达、天文学、电路设计等方面都有应用[3]．优美图是图论中的一个重要分支，研究优美图标号问题有助于研究其他类型的图标号问题，定义一个图的顶点标号是图的顶点集到整数集的映射，边标号是图的边集到整数集的映射[4]．根据对映射的不同要求，新的图标号以及新问题不断涌现．经过多年的研究，目前已经有许多关于优美图的研究成果，也导致了一大批新的标号产生．例如：(k,d)-优美标号、边魔幻标号、反魔幻标号、幸福标号及和谐标号等[5]．

一个图G是二部图，如果它的顶点集V(G)可以分成两个子集X和Y，且图G中的每一条边都有一个顶点在X中，另一个顶点在Y中，图G可以记作G(X，Y)．如果在二部图G(X，Y)中，X中的每个顶点都与Y中每个顶点相连，则称G(X，Y)为完全二部图，若X中有m个顶点，Y中有n个顶点，则完全二部图G(X，Y)记为Km，n[6]．

本文所提到的图都是简单的、无向的并且是有限的，所定义的记号同文献[4]．为叙述方便，把一个有p个顶点和q条边的图叫做(p，q)-图G．设(p，q)-图G有一个映射f：V(G)→[0，q]．记f(V(G))={f(u)：u∈V(G)}，f(E(G))={f(uv)=|f(u)-f(v)|：uv∈E(G)}．

本文中用到的[m，n]是指集合{m，m+1，m+2，…，n}，即从m到n的自然数；[s，t]o表示奇数集合{s,s+2，s+4，…，t}，即从s到t的全体奇数；[k，l]e表示偶数集合{k，k+2，k+4，…，l}，即从k到l的全体偶数[7]．文中未给出的符号及定义参见文献[4]．

1 基本概念

定义1[5-7]如果(p，q)-图G有一个映射f：V(G)→[0，q]，使得图G中任意两个顶点x、y满足f(x)≠f(y)且定义边uv∈E(G)的标号为f(uv)=|f(u)-f(v)|．当{f(uv)：uv∈E(G)}=[1，q]时，则称f为图G的一个优美标号，图G为优美图．

定义2[8]对于给定的(p，q)-图G，如果存在一个映射f：V(G)→[0，k+(q-1)d]，使得图G中任意两个顶点x、y满足f(x)≠f(y)且边标号集合f(E(G))={k，k+d，k+2d，…，k+(q-1)d}，则称f为图G的一个(k，d)-优美标号，图G为(k，d)-优美图．

定义3对于给定的(p，q)-图G，如果存在一个映射f：V(G)→[0，2q-1]，使得图G中任意两个顶点x、y满足f(x)≠f(y)且定义边uv∈E(G) 的标号为f(uv)=f(u)+f(v)．当{f(uv)：uv∈E(G)}=[1，2q-1]o时，则称f为图G的一个奇边魔幻全标号，图G为奇边魔幻图．

图1是组合完全二部图的示意图，它由支架与完全二部图组成，而支架是由顶点a1，a2，…，as依次连接，完全二部图则是由图Gi(i∈[1，s])构成，Gi即为Km，n．其中V(Gi)={ai，bi,t，ci,k|t∈[1，m]，k∈[1，n]，i∈[1，s]}，E(Gi)={aibi,1，bi,tci,k，aiai+1|t∈[1，m]，k∈[1，n]，i∈[1，s]}，再将每个完全二部图Gi中的ai(i∈[1，s])相连．

图1 一个组合完全二部图

图2是串联完全二部图示意图，它由n个完全二部图依次连接而成，完全二部图则是由图Gi构成，Gi即为Kmi，ni，其中V(Gi)={bi,ti，ci,ki|i∈[1，s]，ti∈[1，mi]，ki∈[1，ni]}，E(Gi)={bi,tici,ki，bi,1ci-1，n|i∈[1，s]，ti∈[1，mi]，ki∈[1，ni]}．

图2 一个串联完全二部图

2 主要结论

定理1组合完全二部图具有奇边魔幻标号．

证明设图G是组合完全二部图，定义图G的一个标号f：令f(b1,1)=0．对i∈[1，s]，t∈[1，m]，k∈[1，n]分情形证明．

若m=3，n=4．当s=1时，有

f(b1,2)=8，f(b1,3)=16；f(c1,1)=1，

f(c1,2)=3，f(c1,3)=5，f(c1,4)=7；

f(b1,tc1,k)=2(t-1)n+(2k-1)；

f(a1b1,1)=f(b1,3c1,4)+2

即结论成立．

当s≥2，i为奇数，且m、n为任意数时，边标号如下：

f(bi,tci,k)=2(mn+2)(i-1)+2n(t-1)+

2k-1；

f(aibi,1)=2mn+1+2(mn+2)(i-1)；

f(aiai+1)=2mn+3+2(mn+2)(i-1)

当i为偶数时，边标号如下：

f(bi,tci,k)=2m+7+2(mn-1)-2(k-1)-

2(t-1)n+2(mn+2)(i-2)；

f(aibi,1)=2mn+5+2(mn+2)(i-2)；

f(aiai+1)=2mn+9+2(mn-1)+

2(mn+2)(i-2)

顶点标号如下：

f(a1)=f(a1b1,1)-f(b1,1)；

f(ai+1)=f(aiai+1)-f(ai)；

f(bi,1)=f(aibi,1)-f(ai)；

f(ci,k)=f(bi,1ci,k)-f(bi,1)；

f(bi,t)=f(bi,tci,k)-f(ci,k)；

f(c1,k)=f(b1,1c1,k)-f(b1,1)；

f(b1,t)=f(b1,tc1,k)-f(c1,k)

根据上述标号可知，图G的边f(bi,tci,k)、f(aibi,1)、f(aiai+1)标号均为奇数．

下证所有边标号在[1，2q-1]o中．在上述的公式中可知，当i=1时，f(b1,1c1,1)=1是最小的，f(b1,1c1,2)=3，f(b1,1c1,3)=5．类推得f(b1,1c1,n)=2n-1，则这n条边的边标号均在[1，2n-1]o中．

将f(b1,1c1,1)代入上述式中可得f(b1,2c1,1)=2n+1，f(b1,2c1,2)=2n+3，…，f(b1,2c1,n)=4n-1，则这n条边的边标号被包含在[2n+1，4n-1]o里．

由公式知，f(b1,mc1,1)=2n(m-1)+1，f(b1,mc1,2)=2n(m-1)+3，…，f(b1,mc1,n)=2nm-1，由f(b1,mc1,1)，f(b1,m，c1,2)，…，f(b1,mc1,n)构成的集合为[2n(m-1)+1，2nm-1]o．

当i=1时，f(a1b1,1)=2nm+1，f(a1a2)=2nm+3．

当i=2时，f(b2,mc2,n)=2nm+7，f(b2,mc2,n-1)=2nm+9，…，f(b2,mc2,1)=2n(m+1)+5，显然n条边的边标号所在的集合为[2nm+7，2n(m+1)+5]o．且f(a2b2,1)=2nm+5．

当i=2，t=m-1，k=n时，f(b2,m-1c2,n)=2n(m+1)+7，f(b2,m-1c2,n-1)=2n(m+1)+9，依此类推，得出f(b2,m-1c2,1)=2n(m+2)+5，有

{f(b2,m-1c2,n)，f(b2,m-1c2,n-1)，…，f(b2,m-1c2,1)}=[2n(m+1)+7，2n(m+2)+5]o

当i=2，t=1，k=n时，f(b2,1c2,n)=4mn-2n+7，f(b2,1c2,n-1)=4mn-2n+9，…，f(b2,1c2,1)=4mn+5，则这n条边的边标号包含在[4mn-2n+7，4mn+5]o中．且f(a2a3)=4mn+7．

当i=3时，f(b3,1c3,1)=4mn+9．依次下去标出整个图．若s为奇数，则最大的边标号为f(asbs,1)=2(smn+2s-1)-1；若s为偶数，则最大的边标号为f(bs,1cs,1)=2(smn+2s-1)-1．

由上述标号可得f(V(G))→[0，2q-1]，f(E(G))=[1，2q-1]o(其中q=smn+2s-1，表示图的总边数)，f(uv)=f(u)+f(v)．则f是一个奇边魔幻全标号，图G是奇边魔幻图．

一个具有奇边魔幻全标号的组合完全二部图在图3中给出．

图3 奇边魔幻全标号图

定理2若图G是串联完全二部图，则图G有优美标号．

证明对于完全二部图Km，n，其中X中有m个点，Y中有n个点，则完全二部图Km，n有mn条边，有如图4所示的优美标号．设f为图G的标号．

f(b1,2)=1，f(b1,3)=2；f(c1,1)=31，

f(c1,2)=28，f(c1,3)=25，f(c1,4)=22；

f(b2,1)=3，f(b2,2)=4，f(b2,3)=5；

f(c2,1)=21，f(c2,2)=18，f(c2,3)=15，

f(c2,4)=12，f(c2,5)=9，f(c2,6)=6；

f(b2,3c2,6)=1，f(b2,2c2,6)=2，f(b2,1c2,6)=3；

f(b2,3c2,5)=4，f(b2,2c2,5)=5，f(b2,1c2,5)=6；

f(b2,3c2,4)=7，f(b2,2c2,4)=8，f(b2,1c2,4)=9；

f(b2,3c2,3)=10，f(b2,2c2,3)=11，f(b2,1c2,3)=12；

f(b2,3c2,2)=13，f(b2,2c2,2)=14，f(b2,1c2,2)=15；

f(b2,3c2,1)=16，f(b2,2c2,1)=17，f(b2,1c2,1)=18；

f(b2,1c1,4)=19；f(b1,3c1,4)=20，f(b1,2c1,4)=21，

f(b1,1c1,4)=22；f(b1,3c1,3)=23，f(b1,2c1,3)=24，

f(b1,1c1,3)=25；f(b1,3c1,2)=26，f(b1,2c1,2)=27，

f(b1,1c1,2)=28；f(b1,3c1,1)=29，f(b1,2c1,1)=30，

f(b1,1c1,1)=31

可知它满足优美标号的条件．

图4 一个完全二部图

推广到一般情况可按以下过程进行顶点标号：

f(b1,1)=0；f(bi,t)=(i-1)m+(t-1)；

f(ci,ki)=f(ci-1，n)-1-(ki-1)m

可按以下过程进行边标号：f(ci,kibi,t)=f(ci,ki)-f(bi,t)；f(ci,nbi+1，1)=f(ci,n)-f(bi+1，1)．其中i∈[1，s]，t∈[1，m]，ki∈[1，ni]．

可知，f(b1,1c1,1)，f(b1,2c1,1)，f(b1,3c1,1)，…，f(b1,mc1,1)分别是q，q-1，q-2，…，q-m+1；f(b1,1c1,2)，f(b1,2c1,2)，f(b1,3c1,2)，…，f(b1,mc1,2)分别等于q-m，q-m-1，q-m-2，…，q-2m+1；依次下去，f(b1,1c1,n1)，f(b1,2c1,n1)，f(b1,3c1,n1)，…，f(b1,mc1,n1)的值是q-(n1-1)m，q-(n1-1)m-1，q-(n1-1)m-2，…，q-n1m+1；…；f(b2,1c1,n1)=q-n1m，f(b2,1c2,1)，f(b2,2c2,1)，f(b2,3c2,1)，…，f(b2,mc2,1)为q-n1m-1，q-n1m-2，q-n1m-3，…，q-(n1+1)m．

边b2,1c2,2，b2,2c2,2，b2,3c2,2，…，b2,mc2,2所对应的标号分别为q-(n1+1)m-1，q-(n1+1)m-2，q-(n1+1)m-3，…，q-(n1+2)m；依次下去，f(b2,1c2,n2)，f(b2,2c2,n2)，f(b2,3c2,n2)，…，f(b2,mc2,n2)分别为q-(n1+n2-1)m-1，q-(n1+n2-1)m-2，q-(n1+n2-1)m-3，…，q-(n1+n2)m；f(b2,mc3,1)=q-(n1+n2)m-1，…，f(bs-1，mcs,1)=nsm+1，f(bs,1cs,1)，f(bs,2cs,1)，f(bs,3cs,1)，…，f(bs,mcs,1)与数值nsm，nsm-1，nsm-2，…，(ns-1)m+1对应相等；f(bs,1cs,2)，f(bs,2cs,2)，f(bs,3cs,2)，…，f(bs,mcs,2)的值是(ns-1)m，(ns-1)m-1，(ns-1)m-2，…，(ns-2)m+1；依次下去，f(bs,1cs,ns)，f(bs,2cs,ns)，f(bs,3cs,ns)，…，f(bs,mcs,ns)与m，m-1，m-2，…，1对应相等．

若n=3，m1=4，m2=6．当s=2时，有

f(b1,1)=0，f(b1,2)=1，f(b1,3)=2，

f(b1,4)=3；f(c1,1)=31，f(c1,2)=27，

f(c1,3)=23；f(b2,1)=4，f(b2,2)=5，

f(b2,3)=6，f(b2,4)=7，f(b2,5)=8，

f(b2,6)=9；f(c2,1)=22，f(c2,2)=16，

f(c2,3)=10；f(b2,6c2,3)=1，f(b2,5c2,3)=2，

f(b2,4c2,3)=3，f(b2,3c2,3)=4，f(b2,2c2,3)=5，

f(b2,1c2,3)=6；f(b2,6c2,2)=7，f(b2,5c2,2)=8，

f(b2,4c2,2)=9，f(b2,3c2,2)=10，f(b2,2c2,2)=11，

f(b2,1c2,2)=12；f(b2,6c2,1)=13，f(b2,5c2,1)=14，

f(b2,4c2,1)=15，f(b2,3c2,1)=16，f(b2,2c2,1)=17，

f(b2,1c2,1)=18；f(b2,1c1,3)=19；f(b1,4c1,3)=20，

f(b1,3c1,3)=21，f(b1,2c1,3)=22，f(b1,1c1,3)=23；

f(b1,4c1,2)=24，f(b1,3c1,2)=25，f(b1,2c1,2)=26，

f(b1,1c1,2)=27；f(b1,4c1,1)=28，f(b1,3c1,1)=29，

f(b1,2c1,1)=30，f(b1,1c1,1)=31

可知它满足优美标号的条件．

当s>2时，有以下标号过程：

f(b1,1)=0，f(b1,t1)=t1-1，

f(b2,t2)=n1+(t2-1)，

f(b3,t3)=(n1+n2)+(t3-1)，

f(c2,1)=f(c1,n)-1，

f(c2,k)=f(c2,1)-m2(k-1)，

f(ci,1)=f(ci-1，n)-1，

f(ci,k)=f(ci,1)-mi(k-1)

图G的边标号按以下方程进行：

f(ci,kbi,t)=f(ci,k)-f(bi,t)；

f(ci,nbi+1，1)=f(ci,n)-f(bi+1，1)

有f(b1,1c1,1)，f(b1,2c1,1)，f(b1,3c1,1)，…，f(b1,m1c1,1) 分别等于q，q-1，q-2，…，q-m1+1；边b1,1c1,2，b1,2c1,2，b1,3c1,2，…，b1,mc1,2的标号分别为q-m1，q-m1-1，q-m1-2，…，q-2m1+1；…；f(b1,1c1,n1)，f(b1,2c1,n1)，f(b1,3c1,n1)，…，f(b1,m1c1,n1) 分别为q-(n-1)m1，q-(n-1)m1-1，q-(n-1)m1-2，…，q-nm1+1；依次下去，f(b2,1c1,n)=q-nm1，f(b2,1c2,1)，f(b2,2c2,1)，f(b2,3c2,1)，…，f(b2,m2c2,1)的值为q-nm1-1，q-nm1-2，q-nm1-3，…，q-nm1-m2；f(b2,1c2,2)，f(b2,2c2,2)，f(b2,3c2,2)，…，f(b2,m2c2,2) 分别为q-nm1-m2-1，q-nm1-m2-2，q-nm1-m2-3，…，q-n(m1+m2)；…；f(bs,1cs-1，n)=nms+1，f(bs,1cs,1)，f(bs,2cs,1)，f(bs,3cs,1)，…，f(bs,mscs,1)与nms，nms-1，nms-2，…，(n-1)ms+1对应相等；f(bs,1cs,2)，f(bs,2cs,2)，f(bs,3cs,2)，…，f(bs,mscs,2)分别等于(n-1)ms，(n-1)ms-1，(n-1)ms-2，…，(n-2)ms+1；依次下去，f(bs,1cs,n)，f(bs,2cs,n)，f(bs,3cs,n)，…，f(bs,mcs,n)的值是ms，ms-1，ms-2，…，1．

若m1=4，m2=6，n1=3，n2=2．当s=2时，得

f(b1,1)=0，f(b1,2)=1，f(b1,3)=2，

f(b1,4)=3；f(c1,1)=25，f(c1,2)=21，

f(c1,3)=17；f(b2,1)=4，f(b2,2)=5，

f(b2,3)=6，f(b2,4)=7，f(b2,5)=8，

f(b2,6)=9；f(c2,1)=16，f(c2,2)=10；

f(b2,6c2,2)=1，f(b2,5c2,2)=2，f(b2,4c2,2)=3，

f(b2,3c2,2)=4，f(b2,2c2,2)=5，f(b2,1c2,2)=6；

f(b2,6c2,1)=7，f(b2,5c2,1)=8，f(b2,4c2,1)=9，

f(b2,3c2,1)=10，f(b2,2c2,1)=11，f(b2,1c2,1)=12；

f(b2,1c1,3)=13；f(b1,4c1,3)=14，f(b1,3c1,3)=15，

f(b1,2c1,3)=16，f(b1,1c1,3)=17；f(b1,4c1,2)=18，

f(b1,3c1,2)=19，f(b1,2c1,2)=20，f(b1,1c1,2)=21；

f(b1,4c1,1)=22，f(b1,3c1,1)=23，f(b1,2c1,1)=24，

f(b1,1c1,1)=25

可知它满足优美标号的条件．推广到一般情况，可按以下过程进行顶点标号：

f(b1,1)=0，f(b1,t1)=t1-1；

f(b2,t2)=n1+(t2-1)，

f(b3,t3)=n1+n2+(t3-1)，

f(c2,1)=f(c1,n1)-1，

f(c2,k2)=f(c2,1)-m2(k2-1)，

f(ci,1)=f(ci-1，ni-1)-1，

f(ci,ki)=f(ci,1)-mi(ki-1)

由上述顶点标号可推导出图G的边标号：

f(ci,kibi,ti)=f(ci,ki)-f(bi,ti)；

f(ci,nibi+1，1)=f(ci,ni)-f(bi+1，1)

按上述公式标号可知，第一个完全图的边标号：f(b1,1c1,1)，f(b1,2c1,1)，…，f(b1,m1c1,1)，…，f(b1,m1c1,2)，…，f(b1,m1c1,n1)分别为q，q-1，…，q-m1+1，…，q-2m1+1，…，q-n1m1，f(b2,1c1,n1)=q-n1m1-1，按上面的顺序，串联完全二部图的第二个完全二部图的边标号在[q-(n1m1+n2m2-2，q-n1m1-2)]内，f(b3,1c2,n2)=q-(n1m1+n2m2-3)，…，f(bs,1cs-1，n)=nms+1，f(bs,1cs,1)，f(bs,2cs,1)，f(bs,3cs,1)，…，f(bs,mscs,1)分别为nms，nms-1，nms-2，…，(n-1)ms+1；f(bs,1cs,2)，f(bs,2cs,2)，f(bs,3cs,2)，…，f(bs,mscs,2)为(n-1)ms，(n-1)ms-1，(n-1)ms-2，…，(n-2)ms+1；依次下去，f(bs,1cs-1，ns-1)=nsms+1，第s个完全二部图的边标号在[1，nsms]中．

综上，可得标号f满足f：V(G)→[0，q]，f(E(G))=[1，q]，则串联完全二部图G为优美图，f为图G的一个优美标号．

□

推论1每个串联完全二部图G都有(k，d)-优美标号．

证明类似定理1的分类，进行讨论．

g(b1,1)=f(b1,1)d，g(bi,t)=f(bi,t)d；

g(c1,1)=k+(f(c1,1)-1)d，

g(c1,k1)=k+(f(c1,k1)-1)d，

g(ci,ki)=(f(ci,ki)-1)+k；

g(ci,kibi,t)=g(ci,ki)-g(bi,t)，

g(ci,nbi+1，1)=g(ci,n)-g(bi+1，1)

其中i∈[1，s]，t∈[1，m]，ki∈[1，ni]．

g(b1,1)=f(b1,1)d，g(bi,ti)=f(bi,ti)d；

g(c1,1)=k+(f(c1,1)-1)d，

g(c1,k)=k+(f(c1,k)-1)d，

g(ci,k)=(f(ci,k)-1)d+k；

g(ci,kbi,ti)=g(ci,k)-g(bi,ti)，

g(ci,nbi+1，1)=g(ci,n)-g(bi+1，1)

其中i∈[1，s]，ti∈[1，mi]，k∈[1，n]．

g(b1,1)=f(b1,1)d，g(b1,t1)=f(b1,t1)d，

g(bi,ti)=f(bi,ti)d；

g(c1,1)=(f(c1,1)-1)d+k，

g(c1,k1)=(f(c1,k1)-1)d+k；

g(c2,1)=(f(c2,1)-1)d+k，

g(c2,k2)=(f(c2,k2)-1)d+k，

g(ci,1)=(f(ci,1)-1)d+k，

g(ci,ki)=(f(ci,ki)-1)d+k；

g(ci,kibi,ti)=g(ci,ki)-g(bi,ti)，

g(ci,nibi+1，1)=g(ci,ni)-g(bi+1，1)

其中i∈[1，s]，ti∈[1，mi]，ki∈[1，ni]．

综上，标号g满足g：V(G)→[0，k+(q-1)d] 和f(E(G))={k，k+d，k+2d，…，k+(q-1)d}，则串联完全二部图为(k，d)-优美图，标号g为的它一个(k，d)-优美标号．

□

3 结 语

本文对完全二部图的一些性质做了简要总结，并且在其他标号的基础上研究出一类新的标号：奇边魔幻标号．先对奇边魔幻标号、组合完全二部图、串联完全二部图进行定义，对组合完全二部图、串联完全二部图的性质进行了简单分析，并且证明了组合完全二部图是奇边魔幻图，串联完全二部图是优美图．当然，本文是从最基本的方法出发，显然不够深刻，还需要大量的后续工作来进一步探寻奇边优美标号的性质，以及该标号和这类完全二部图在日常生活中的应用等，从而进一步完善部分完全图的各类标号．

[1] RINGEL G. Problem 25 in theory of graphs and its application [C] // FLEDLER M, ed.Proceedingofthe4thInternationalSymposiumSmolenice. Prague: Czech Academy of Science, 1963:162-167.

[2] ROSA A.OnCertainValuationofVerticesofGraph[M]. New York: Gordon and Breach, 1966:349-355.

[3] 李振汉,唐余亮,雷 鹰. 基于ZigBee的无线传感器网络的自愈功能[J]. 厦门大学学报(自然科学版), 2012,51(5):834-838.

LI Zhenhan, TANG Yuliang, LEI Ying. Self-healing function based on wireless sensor networks of ZigBee [J].JournalofXiamenUniversity(NaturalScience), 2012,51(5):834-838. (in Chinese)

[4] BONDY J A, MURTY U S R.GraphTheorywithApplications[M]. New York: The Macmillan Press,1976.

[5] YAO Bing, YAO Ming, CHEN Xiang′en,etal. Research on edge-growing models related with scale-free small-world networks [J].AppliedMechanicsandMaterials, 2013,513-517:2444-2448.

[6] GALLIAN J A. A dynamic survey of graph labelling [J].TheElectronicJournalofCombinatorics, 2000,6:10-18.

[7] LI Lun, ALDERSON D, DOYLE J C,etal. Towards a theory of scale-free graphs: definition,properties, and implications [J].InternetMathematics, 2005,2(4):431-523.

[8] ACHARYA B D, HEDGE S M J. Graph theory [J].ArithmeticGraphs, 1990,2:275-299.

Explorationofgracefulnessofsomecompletebipartitegraphs

BALina,LIUQian,LIUXinsheng,YAOBing*

(CollegeofMathematicsandStatistics,NorthwestNormalUniversity,Lanzhou730070,China)

The bipartite graphs of graph theory and graph labellings are widely used in practical applications, especially recently the graph labelling has been applied to design a new type of graphical password. Firstly, some complete bipartite graphs are constructed by combinatoric and series methods. A new labelling, called edge-odd-magical total labelling, is found and it is proved that the combinatoric complete bipartite graphs admit the edge-odd-magical total labelling. Moreover, series complete bipartite graphs are graceful, or (k,d)-graceful.

trees; complete bipartite graph; graceful labelling; (k,d)-graceful labelling

1000-8608(2017)06-0657-06

O157.5

A

10.7511/dllgxb201706016

2017-05-13；

2017-10-13．

国家自然科学基金资助项目(61163037,61163054,61363060)．

把丽娜(1992-)，女，硕士生，E-mail:917622578@qq.com；姚 兵*(1956-)，男，教授，E-mail:yybb918@163.com.