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

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

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

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

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

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

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

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

0 引 言

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

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

本文所提到的圖都是簡(jiǎn)單的、無(wú)向的并且是有限的，所定義的記號(hào)同文獻(xiàn)[4]．為敘述方便，把一個(gè)有p個(gè)頂點(diǎn)和q條邊的圖叫做(p，q)-圖G．設(shè)(p，q)-圖G有一個(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]．文中未給出的符號(hào)及定義參見文獻(xiàn)[4]．

1 基本概念

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

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

定義3對(duì)于給定的(p，q)-圖G，如果存在一個(gè)映射f：V(G)→[0，2q-1]，使得圖G中任意兩個(gè)頂點(diǎn)x、y滿足f(x)≠f(y)且定義邊uv∈E(G) 的標(biāo)號(hào)為f(uv)=f(u)+f(v)．當(dāng){f(uv)：uv∈E(G)}=[1，2q-1]o時(shí)，則稱f為圖G的一個(gè)奇邊魔幻全標(biāo)號(hà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]}，再將每個(gè)完全二部圖Gi中的ai(i∈[1，s])相連．

圖1 一個(gè)組合完全二部圖

圖2是串聯(lián)完全二部圖示意圖，它由n個(gè)完全二部圖依次連接而成，完全二部圖則是由圖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 一個(gè)串聯(lián)完全二部圖

2 主要結(jié)論

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

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

若m=3，n=4．當(dāng)s=1時(shí)，有

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ù)時(shí)，邊標(biāo)號(hà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ù)時(shí)，邊標(biāo)號(hà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)號(hà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)號(hào)可知，圖G的邊f(xié)(bi,tci,k)、f(aibi,1)、f(aiai+1)標(biāo)號(hào)均為奇數(shù)．

下證所有邊標(biāo)號(hào)在[1，2q-1]o中．在上述的公式中可知，當(dāng)i=1時(shí)，f(b1,1c1,1)=1是最小的，f(b1,1c1,2)=3，f(b1,1c1,3)=5．類推得f(b1,1c1,n)=2n-1，則這n條邊的邊標(biāo)號(hà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)號(hà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時(shí)，f(a1b1,1)=2nm+1，f(a1a2)=2nm+3．

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

當(dāng)i=2，t=m-1，k=n時(shí)，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時(shí)，f(b2,1c2,n)=4mn-2n+7，f(b2,1c2,n-1)=4mn-2n+9，…，f(b2,1c2,1)=4mn+5，則這n條邊的邊標(biāo)號(hào)包含在[4mn-2n+7，4mn+5]o中．且f(a2a3)=4mn+7．

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

由上述標(biāo)號(hà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是一個(gè)奇邊魔幻全標(biāo)號(hào)，圖G是奇邊魔幻圖．

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

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

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

證明對(duì)于完全二部圖Km，n，其中X中有m個(gè)點(diǎn)，Y中有n個(gè)點(diǎn)，則完全二部圖Km，n有mn條邊，有如圖4所示的優(yōu)美標(biāo)號(hào)．設(shè)f為圖G的標(biāo)號(hà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)號(hào)的條件．

圖4 一個(gè)完全二部圖

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

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

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

可按以下過(guò)程進(jìn)行邊標(biāo)號(hà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所對(duì)應(yīng)的標(biāo)號(hà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對(duì)應(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對(duì)應(yīng)相等．

若n=3，m1=4，m2=6．當(dāng)s=2時(shí)，有

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)號(hào)的條件．

當(dāng)s>2時(shí)，有以下標(biāo)號(hào)過(guò)程：

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)號(hà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)號(hà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對(duì)應(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時(shí)，得

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)號(hào)的條件．推廣到一般情況，可按以下過(guò)程進(jìn)行頂點(diǎn)標(biāo)號(hà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)號(hào)可推導(dǎo)出圖G的邊標(biāo)號(hà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)號(hào)可知，第一個(gè)完全圖的邊標(biāo)號(hà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)完全二部圖的第二個(gè)完全二部圖的邊標(biāo)號(hà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個(gè)完全二部圖的邊標(biāo)號(hào)在[1，nsms]中．

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

□

推論1每個(gè)串聯(lián)完全二部圖G都有(k，d)-優(yōu)美標(biāo)號(hà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)號(hà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)號(hào)g為的它一個(gè)(k，d)-優(yōu)美標(biāo)號(hào)．

□

3 結(jié) 語(yǔ)

本文對(duì)完全二部圖的一些性質(zhì)做了簡(jiǎn)要總結(jié)，并且在其他標(biāo)號(hào)的基礎(chǔ)上研究出一類新的標(biāo)號(hào)：奇邊魔幻標(biāo)號(hào)．先對(duì)奇邊魔幻標(biāo)號(hào)、組合完全二部圖、串聯(lián)完全二部圖進(jìn)行定義，對(duì)組合完全二部圖、串聯(lián)完全二部圖的性質(zhì)進(jìn)行了簡(jiǎn)單分析，并且證明了組合完全二部圖是奇邊魔幻圖，串聯(lián)完全二部圖是優(yōu)美圖．當(dāng)然，本文是從最基本的方法出發(fā)，顯然不夠深刻，還需要大量的后續(xù)工作來(lái)進(jìn)一步探尋奇邊優(yōu)美標(biāo)號(hào)的性質(zhì)，以及該標(biāo)號(hào)和這類完全二部圖在日常生活中的應(yīng)用等，從而進(jìn)一步完善部分完全圖的各類標(biāo)號(hà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ú)線傳感器網(wǎng)絡(luò)的自愈功能[J]. 廈門大學(xué)學(xué)報(bào)(自然科學(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．

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

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