完全二部圖優(yōu)美性質(zhì)探索

把麗娜， 劉 倩， 劉信生， 姚 兵

( 西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 甘肅 蘭州 730070 )

完全二部圖優(yōu)美性質(zhì)探索

把麗娜， 劉 倩， 劉信生， 姚 兵*

( 西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 甘肅 蘭州 730070 )

圖論的二部圖及其標(biāo)號在實(shí)際應(yīng)用中較多，尤其最近圖標(biāo)號被應(yīng)用于新型的圖形密碼設(shè)計(jì)．首先構(gòu)造出了組合完全二部圖與串聯(lián)完全二部圖，發(fā)現(xiàn)了一種叫做奇邊魔幻全標(biāo)號的標(biāo)號，并給出了組合完全二部圖具有奇邊魔幻全標(biāo)號的證明．此外，得出了串聯(lián)完全二部圖是優(yōu)美圖、(k，d)-優(yōu)美圖的結(jié)論．

樹；完全二部圖；優(yōu)美標(biāo)號；(k，d)-優(yōu)美標(biāo)號

0 引 言

圖的標(biāo)號設(shè)計(jì)是圖論中具有實(shí)際應(yīng)用背景的研究課題．在圖論的研究中，圖的第一個標(biāo)號問題是在20世紀(jì)60年代由Ringel[1]提出的，人們根據(jù)應(yīng)用的需要發(fā)現(xiàn)了許多關(guān)于簡單圖的標(biāo)號和猜想．優(yōu)美圖是圖的標(biāo)號理論中十分重要的課題之一．1966年，Rosa在其關(guān)于圖同構(gòu)分解問題的研究中提出了關(guān)于優(yōu)美樹的猜想，認(rèn)為“所有的樹圖都是優(yōu)美的”[2]．猜想的提出引起了圖論研究者的廣泛關(guān)注，使得包括優(yōu)美標(biāo)號、奇優(yōu)美標(biāo)號在內(nèi)的圖標(biāo)號問題研究得到了空前的發(fā)展．圖的優(yōu)美標(biāo)號問題是組合數(shù)學(xué)研究專題，它不僅屬于圖論的領(lǐng)域而且在設(shè)計(jì)理論的范疇．優(yōu)美圖在物流運(yùn)輸、編碼理論、雷達(dá)、天文學(xué)、電路設(shè)計(jì)等方面都有應(yīng)用[3]．優(yōu)美圖是圖論中的一個重要分支，研究優(yōu)美圖標(biāo)號問題有助于研究其他類型的圖標(biāo)號問題，定義一個圖的頂點(diǎn)標(biāo)號是圖的頂點(diǎn)集到整數(shù)集的映射，邊標(biāo)號是圖的邊集到整數(shù)集的映射[4]．根據(jù)對映射的不同要求，新的圖標(biāo)號以及新問題不斷涌現(xiàn)．經(jīng)過多年的研究，目前已經(jīng)有許多關(guān)于優(yōu)美圖的研究成果，也導(dǎo)致了一大批新的標(biāo)號產(chǎn)生．例如：(k,d)-優(yōu)美標(biāo)號、邊魔幻標(biāo)號、反魔幻標(biāo)號、幸福標(biāo)號及和諧標(biāo)號等[5]．

一個圖G是二部圖，如果它的頂點(diǎn)集V(G)可以分成兩個子集X和Y，且圖G中的每一條邊都有一個頂點(diǎn)在X中，另一個頂點(diǎn)在Y中，圖G可以記作G(X，Y)．如果在二部圖G(X，Y)中，X中的每個頂點(diǎn)都與Y中每個頂點(diǎn)相連，則稱G(X，Y)為完全二部圖，若X中有m個頂點(diǎn)，Y中有n個頂點(diǎn)，則完全二部圖G(X，Y)記為Km，n[6]．

本文所提到的圖都是簡單的、無向的并且是有限的，所定義的記號同文獻(xiàn)[4]．為敘述方便，把一個有p個頂點(diǎn)和q條邊的圖叫做(p，q)-圖G．設(shè)(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的自然數(shù)；[s，t]o表示奇數(shù)集合{s,s+2，s+4，…，t}，即從s到t的全體奇數(shù)；[k，l]e表示偶數(shù)集合{k，k+2，k+4，…，l}，即從k到l的全體偶數(shù)[7]．文中未給出的符號及定義參見文獻(xiàn)[4]．

1 基本概念

定義1[5-7]如果(p，q)-圖G有一個映射f：V(G)→[0，q]，使得圖G中任意兩個頂點(diǎn)x、y滿足f(x)≠f(y)且定義邊uv∈E(G)的標(biāo)號為f(uv)=|f(u)-f(v)|．當(dāng){f(uv)：uv∈E(G)}=[1，q]時，則稱f為圖G的一個優(yōu)美標(biāo)號，圖G為優(yōu)美圖．

定義2[8]對于給定的(p，q)-圖G，如果存在一個映射f：V(G)→[0，k+(q-1)d]，使得圖G中任意兩個頂點(diǎn)x、y滿足f(x)≠f(y)且邊標(biāo)號集合f(E(G))={k，k+d，k+2d，…，k+(q-1)d}，則稱f為圖G的一個(k，d)-優(yōu)美標(biāo)號，圖G為(k，d)-優(yōu)美圖．

定義3對于給定的(p，q)-圖G，如果存在一個映射f：V(G)→[0，2q-1]，使得圖G中任意兩個頂點(diǎn)x、y滿足f(x)≠f(y)且定義邊uv∈E(G) 的標(biāo)號為f(uv)=f(u)+f(v)．當(dāng){f(uv)：uv∈E(G)}=[1，2q-1]o時，則稱f為圖G的一個奇邊魔幻全標(biāo)號，圖G為奇邊魔幻圖．

圖1是組合完全二部圖的示意圖，它由支架與完全二部圖組成，而支架是由頂點(diǎn)a1，a2，…，as依次連接，完全二部圖則是由圖Gi(i∈[1，s])構(gòu)成，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是串聯(lián)完全二部圖示意圖，它由n個完全二部圖依次連接而成，完全二部圖則是由圖Gi構(gòu)成，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 一個串聯(lián)完全二部圖

2 主要結(jié)論

定理1組合完全二部圖具有奇邊魔幻標(biāo)號．

證明設(shè)圖G是組合完全二部圖，定義圖G的一個標(biāo)號f：令f(b1,1)=0．對i∈[1，s]，t∈[1，m]，k∈[1，n]分情形證明．

若m=3，n=4．當(dāng)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

即結(jié)論成立．

當(dāng)s≥2，i為奇數(shù)，且m、n為任意數(shù)時，邊標(biāo)號如下：

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)

當(dāng)i為偶數(shù)時，邊標(biāo)號如下：

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)

頂點(diǎn)標(biāo)號如下：

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)

根據(jù)上述標(biāo)號可知，圖G的邊f(xié)(bi,tci,k)、f(aibi,1)、f(aiai+1)標(biāo)號均為奇數(shù)．

下證所有邊標(biāo)號在[1，2q-1]o中．在上述的公式中可知，當(dāng)i=1時，f(b1,1c1,1)=1是最小的，f(b1,1c1,2)=3，f(b1,1c1,3)=5．類推得f(b1,1c1,n)=2n-1，則這n條邊的邊標(biāo)號均在[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條邊的邊標(biāo)號被包含在[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)構(gòu)成的集合為[2n(m-1)+1，2nm-1]o．

當(dāng)i=1時，f(a1b1,1)=2nm+1，f(a1a2)=2nm+3．

當(dāng)i=2時，f(b2,mc2,n)=2nm+7，f(b2,mc2,n-1)=2nm+9，…，f(b2,mc2,1)=2n(m+1)+5，顯然n條邊的邊標(biāo)號所在的集合為[2nm+7，2n(m+1)+5]o．且f(a2b2,1)=2nm+5．

當(dāng)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

當(dāng)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條邊的邊標(biāo)號包含在[4mn-2n+7，4mn+5]o中．且f(a2a3)=4mn+7．

當(dāng)i=3時，f(b3,1c3,1)=4mn+9．依次下去標(biāo)出整個圖．若s為奇數(shù)，則最大的邊標(biāo)號為f(asbs,1)=2(smn+2s-1)-1；若s為偶數(shù)，則最大的邊標(biāo)號為f(bs,1cs,1)=2(smn+2s-1)-1．

由上述標(biāo)號可得f(V(G))→[0，2q-1]，f(E(G))=[1，2q-1]o(其中q=smn+2s-1，表示圖的總邊數(shù))，f(uv)=f(u)+f(v)．則f是一個奇邊魔幻全標(biāo)號，圖G是奇邊魔幻圖．

一個具有奇邊魔幻全標(biāo)號的組合完全二部圖在圖3中給出．

圖3 奇邊魔幻全標(biāo)號圖

定理2若圖G是串聯(lián)完全二部圖，則圖G有優(yōu)美標(biāo)號．

證明對于完全二部圖Km，n，其中X中有m個點(diǎn)，Y中有n個點(diǎn)，則完全二部圖Km，n有mn條邊，有如圖4所示的優(yōu)美標(biāo)號．設(shè)f為圖G的標(biāo)號．

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

可知它滿足優(yōu)美標(biāo)號的條件．

圖4 一個完全二部圖

推廣到一般情況可按以下過程進(jìn)行頂點(diǎn)標(biāo)號：

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

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

可按以下過程進(jìn)行邊標(biāo)號：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所對應(yīng)的標(biāo)號分別為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)與數(shù)值nsm，nsm-1，nsm-2，…，(ns-1)m+1對應(yīng)相等；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對應(yīng)相等．

若n=3，m1=4，m2=6．當(dāng)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

可知它滿足優(yōu)美標(biāo)號的條件．

當(dāng)s>2時，有以下標(biāo)號過程：

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的邊標(biāo)號按以下方程進(jìn)行：

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的標(biāo)號分別為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對應(yīng)相等；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．當(dāng)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

可知它滿足優(yōu)美標(biāo)號的條件．推廣到一般情況，可按以下過程進(jìn)行頂點(diǎn)標(biāo)號：

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)

由上述頂點(diǎn)標(biāo)號可推導(dǎo)出圖G的邊標(biāo)號：

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

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

按上述公式標(biāo)號可知，第一個完全圖的邊標(biāo)號：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，按上面的順序，串聯(lián)完全二部圖的第二個完全二部圖的邊標(biāo)號在[q-(n1m1+n2m2-2，q-n1m1-2)]內(nèi)，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個完全二部圖的邊標(biāo)號在[1，nsms]中．

綜上，可得標(biāo)號f滿足f：V(G)→[0，q]，f(E(G))=[1，q]，則串聯(lián)完全二部圖G為優(yōu)美圖，f為圖G的一個優(yōu)美標(biāo)號．

□

推論1每個串聯(lián)完全二部圖G都有(k，d)-優(yōu)美標(biāo)號．

證明類似定理1的分類，進(jìn)行討論．

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]．

綜上，標(biāo)號g滿足g：V(G)→[0，k+(q-1)d] 和f(E(G))={k，k+d，k+2d，…，k+(q-1)d}，則串聯(lián)完全二部圖為(k，d)-優(yōu)美圖，標(biāo)號g為的它一個(k，d)-優(yōu)美標(biāo)號．

□

3 結(jié) 語

本文對完全二部圖的一些性質(zhì)做了簡要總結(jié)，并且在其他標(biāo)號的基礎(chǔ)上研究出一類新的標(biāo)號：奇邊魔幻標(biāo)號．先對奇邊魔幻標(biāo)號、組合完全二部圖、串聯(lián)完全二部圖進(jìn)行定義，對組合完全二部圖、串聯(lián)完全二部圖的性質(zhì)進(jìn)行了簡單分析，并且證明了組合完全二部圖是奇邊魔幻圖，串聯(lián)完全二部圖是優(yōu)美圖．當(dāng)然，本文是從最基本的方法出發(fā)，顯然不夠深刻，還需要大量的后續(xù)工作來進(jìn)一步探尋奇邊優(yōu)美標(biāo)號的性質(zhì)，以及該標(biāo)號和這類完全二部圖在日常生活中的應(yīng)用等，從而進(jìn)一步完善部分完全圖的各類標(biāo)號．

[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的無線傳感器網(wǎng)絡(luò)的自愈功能[J]. 廈門大學(xué)學(xué)報(自然科學(xué)版), 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．

國家自然科學(xué)基金資助項(xiàng)目(61163037,61163054,61363060)．

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