連路樹(shù)的全優(yōu)美性

張明軍

(蘭州財(cái)經(jīng)大學(xué)信息工程學(xué)院, 甘肅 蘭州 730020)

連路樹(shù)的全優(yōu)美性

張明軍

(蘭州財(cái)經(jīng)大學(xué)信息工程學(xué)院, 甘肅 蘭州 730020)

圖的標(biāo)號(hào)理論是研究計(jì)算機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)的技術(shù)手段之一.給出了優(yōu)美樹(shù)、二分優(yōu)美樹(shù)、邊對(duì)稱(chēng)樹(shù)以及全優(yōu)美標(biāo)號(hào)的概念，定義了一類(lèi)連路樹(shù)T，并證明了連路樹(shù)T及其邊對(duì)稱(chēng)樹(shù)是全優(yōu)美標(biāo)號(hào)、全優(yōu)美圖.為計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展提供參考.

二分優(yōu)美樹(shù)；優(yōu)美標(biāo)號(hào)；全優(yōu)美標(biāo)號(hào)；邊對(duì)稱(chēng)樹(shù)

1 準(zhǔn)備知識(shí)

圖的標(biāo)號(hào)理論是研究計(jì)算機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)的技術(shù)手段之一.優(yōu)美圖是圖的標(biāo)號(hào)研究中十分重要的課題之一.優(yōu)美圖在物流運(yùn)輸、編碼理論、天文學(xué)等領(lǐng)域均有應(yīng)用.圖的標(biāo)號(hào)問(wèn)題來(lái)自數(shù)學(xué)和圖論學(xué)科自身的問(wèn)題, 甚至是編碼、晶體學(xué)中X-射線的二分性、通信網(wǎng)絡(luò)設(shè)計(jì)中的尋址、最佳電路布局和射電天文等應(yīng)用領(lǐng)域[1,2]. 在優(yōu)美樹(shù)猜想的研究中, 新的標(biāo)號(hào)以及新的問(wèn)題不斷涌現(xiàn)[3]. 本文討論了連路樹(shù)T及其邊對(duì)稱(chēng)樹(shù)是全優(yōu)美標(biāo)號(hào)、全優(yōu)美圖.

本文涉及的圖均為有限、無(wú)向、簡(jiǎn)單圖. 文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均采用文獻(xiàn)[3]. 本文中用記號(hào)[m,n]表示非負(fù)整數(shù)集{m,m+1,m+2,…,n}, 其中m和n均為整數(shù); [k,l]e表示偶數(shù)集{k,k+2,k+4,…,l}, 其中k和l都是偶數(shù), 且滿足0≤k

定義1[3,4].如果一棵n個(gè)頂點(diǎn)的樹(shù)T有一個(gè)正常標(biāo)號(hào)f:V(T)→[0,n-1], 使得邊標(biāo)號(hào)集合f(E(T))={f(uv)|uv∈E(T)}=[1,n-1], 則稱(chēng)T為優(yōu)美樹(shù),f是T的一個(gè)優(yōu)美標(biāo)號(hào).

定義2[5].設(shè) (V1,V2) 是樹(shù)T的頂點(diǎn)集的二部劃分, 如果T有一個(gè)優(yōu)美標(biāo)號(hào)f, 使對(duì)樹(shù)T任意 2 個(gè)頂點(diǎn)x∈V1和y∈V, 總有f(x)

定義3[6].對(duì)于一個(gè)(p,q)-圖G, 如果存在一個(gè)雙射f:V(G)∪E(G)→[1,p+q], 使得邊標(biāo)號(hào)集合f(uv)|uv∈E(G)=[1,q], 其中邊標(biāo)號(hào)為f(uv)=|f(u)-f(v)|,則稱(chēng)G為全優(yōu)美圖(STGG), 并稱(chēng)f為G的一個(gè)全優(yōu)美標(biāo)號(hào) (STGL).

定義4[7].設(shè)T是一棵n階樹(shù),T′ 是T的一個(gè)拷貝, 用一條邊e=xx′將T中的點(diǎn)與其拷貝的同構(gòu)點(diǎn)相連, 得到的新樹(shù)稱(chēng)為樹(shù)T的邊對(duì)稱(chēng)樹(shù).

設(shè)有s條路Pi=ai,0ai,1,…,ai,2m+1(i=1,2,…,s), 用邊連接頂點(diǎn)對(duì)ai,0和ai+1,0(i=1,2,…,s-1), 所得到的樹(shù)稱(chēng)為連路樹(shù)(path-linkedtree), 記為T(mén), 其中ai,j是路Pi上的頂點(diǎn),V(Pi)={ai,j∣j∈[0,2m+1]}, 頂點(diǎn)ai,0,ai+1,0(i=1,2,…,s-1)以及連接他們的邊構(gòu)成路樹(shù)T的主路, 即是Q=a1,0a2,0…as,0. 圖1給出一棵連路樹(shù)T.

2 主要結(jié)果及證明

定理1. 連路樹(shù)T有全優(yōu)美標(biāo)號(hào), 是全優(yōu)美圖.

證明 連路樹(shù)T有n=s(2m+1)個(gè)頂點(diǎn). 下面給出樹(shù)T的標(biāo)號(hào)函數(shù)f:

記V1={ai,j∣(i,j)≡(1,0)(mod2)}∪{ai,j∣(i,j)≡(0,1)(mod2)},

V2={ai,j∣(i,j)≡(1,1)(mod2)}∪{ai,j∣(i,j)≡(0,0)(mod2)}.

fmax(ai,j)=s(m+1)-m-2,i≡1(mod2),j≡0(mod2);

fmax(ai,j)=s(m+1)-1,i≡0(mod2),j≡1(mod2).

即fmax(V1)=s(m+1)-1. 同理能夠得到

fmin(ai,j)=s(m+1),i≡1(mod2),j≡1(mod2);

fmin(ai,j)=s(m+1)+m+1,i≡0(mod2),j≡0(mod2).

即fmin(V2)=s(m+1). 當(dāng)s為偶數(shù)時(shí), 有fmax(V1)

下面證明f是優(yōu)美標(biāo)號(hào).

(2) 證明所有邊標(biāo)號(hào)中沒(méi)有標(biāo)號(hào)相同的邊標(biāo)號(hào). 在E(T)中任取 2 條邊e1=u1u2,e2=v1v2,下面分 4 種情況討論.

情形I: 主路上的邊標(biāo)號(hào)與路Ps上的邊標(biāo)號(hào)不相同.

主路上的邊標(biāo)號(hào)為:f(e1)=|f(ai,0)-f(ai+1,0)|=|n-2(m+1)i|.

路Ps上的邊標(biāo)號(hào)為:

f(e2)=|f(ai,j)-f(ai,j+1)|=|2m+n-2(m+1)i-j+1|,i≡1(mod2),j∈[0,2m]

f(e2)=|f(ai,j)-f(ai,j+1)|=|n-2(m+1)i+j+1|,i≡0(mod2),j∈[0,2m]

當(dāng)i≡1(mod2) 時(shí), 若f(e1)=f(e2), 則一定有2m-j+1=0, 此時(shí)j=2m+1, 與j∈[0,2m]矛盾. 因此,f(e1)≠f(e2). 因?yàn)閖+1≠0, 所以f(e1)≠f(e2) (i≡0(mod2)). 故主路上的邊標(biāo)號(hào)與路Ps上的邊標(biāo)號(hào)都不相同.

情形II: 主路Ps上的邊標(biāo)號(hào)互不相同. 由于

f(e1)=|f(ap,0)-f(ap+1,0)|=|n-2p(m+1)|;

f(e2)=|f(aq,0)-f(aq+1,0)|=|n-2q(m+1)|.

其中p,q∈[1,s-1],p≠q

所以,f(e1)-f(e2)=2|(m+1)(p-q)|≠0(p≠q),即主路上的邊標(biāo)號(hào)互不相同.

情形III: 同一條路Ps上的邊標(biāo)號(hào)互不相同. 若i≡1(mod2), 得

f(e1)=|f(ai,k)-f(ai,k+1)|=|2m+n-2(m+1)i-k+1|;

f(e2)=|f(ai,l)-f(ai,l+1)|=|2m+n-2(m+1)i-l+1|.

其中k,l∈[0,2m],k≠l.

因?yàn)閗≠l, 顯然有f(e1)≠f(e2). 若i≡0(mod2), 有

f(e1)=|f(ai,k)-f(ai,k+1)|=|n-2(m+1)i+k+1|;

f(e2)=|f(ai,l)-f(ai,l+1)|=|n-2(m+1)i+l+1|.

其中k,l∈[0,2m],k≠l.

注意到k≠l, 故f(e1)-f(e2)=|k-l|≠0. 可斷言, 路Ps上的邊標(biāo)號(hào)互不相同.

情形IV: 不同的路Pi1和Pi2(i1≠i2,i1,i2∈s) 上的邊標(biāo)號(hào)互不相同.

(i) 若i1,i2≡1(mod2), 則有

f(e1)=|f(ai1,k)-f(ai1,k+1)|=|2m+n-2(m+1)i1-k+1|;

f(e2)=|f(ai2,l)-f(ai2,l+1)|=|2m+n-2(m+1)i2-l+1|.

其中k,l∈[0,2m].

假設(shè)f(e1)=f(e2), 即就是 2(m+1)i1+k=2(m+1)i2+l, 從而有2(m+1)(i1-i2)=l-k.

這里l-k∈[-2m,2m], 顯然矛盾,f(e1)≠f(e2)成立.

(ii) 若i1,i2≡0(mod2), 因有

f(e1)=|f(ai1,k)-f(ai1,k+1)|=|n-2(m+1)i1+k+1|;

f(e2)=|f(ai2,l)-f(ai2,l+1)|=|n-2(m+1)i2+l+1|.

其中k,l∈[0,2m].

與 (i) 中證明類(lèi)似, 同理可得f(e1)≠f(e2).

(iii) 當(dāng)i1≡1(mod2) 和i2≡0(mod2) 時(shí), 有

f(e1)=|f(ai1,k)-f(ai1,k+1)|=|2m+n-2(m+1)i1-k+1|;

f(e2)=|f(ai2,l)-f(ai2,l+1)|=|n-2(m+1)i2+l+1|.

其中k,l∈[0,2m].

假定f(e1)=f(e2), 就有 2m-2(m+1)i1-k=-2(m+1)i2+l, 也就是2(m+1)(i1-i2) +k+l=2m. 如果i1>i2, 則有 (i1-i2)min=1. 但是, 2(m+1)(i1-i2)+k+l=2m+2+k+l>2m矛盾. 如果i1

綜上所述, 所有邊標(biāo)號(hào)中沒(méi)有相同的邊標(biāo)號(hào).即f(E(T))=[1,n-1].又fmax(V1)

因此, 連路樹(shù)T是二分優(yōu)美樹(shù).

(3)下面證明連路樹(shù)T有全優(yōu)美標(biāo)號(hào), 是全優(yōu)美圖.

連路樹(shù)T有n個(gè)頂點(diǎn)和n-1 條邊的二分優(yōu)美樹(shù), (V1,V2) 是它的頂點(diǎn)集的二部劃分,f是T的一個(gè)集有序優(yōu)美標(biāo)號(hào). 給出連路樹(shù)T的一個(gè)新標(biāo)號(hào)：h(ai,j)=n+f(ai,j). 則f(E(T))=[1,n-1],.f(V(T))=[n,2n-1]，E(T)∪V(T)=[1,2n-1]=[1,p+q] (p,q分別表示連路樹(shù)T的頂點(diǎn)數(shù)和邊數(shù)).又f(E(T))=[1,n-1], 所以, 連路樹(shù)T有全優(yōu)美標(biāo)號(hào), 是全優(yōu)美圖(STGG).

圖2、圖3是解釋定理 1 的一個(gè)例子.

圖2 18個(gè)頂點(diǎn)連路樹(shù)的全優(yōu)美標(biāo)號(hào)

圖3 32個(gè)頂點(diǎn)連路樹(shù)的全優(yōu)美標(biāo)號(hào)

定理2.連路樹(shù)T的邊對(duì)稱(chēng)樹(shù)是全優(yōu)美標(biāo)號(hào), 全優(yōu)美圖.

下面證明連路樹(shù)T的邊對(duì)稱(chēng)樹(shù)H有全優(yōu)美標(biāo)號(hào), 是全優(yōu)美圖.

由上述證明可知連路樹(shù)T的邊對(duì)稱(chēng)樹(shù)H是一個(gè)有2n個(gè)頂點(diǎn)和 2n-1條邊的二分優(yōu)美樹(shù).h是邊對(duì)稱(chēng)樹(shù)H的一個(gè)集有序優(yōu)美標(biāo)號(hào). 下面給出邊對(duì)稱(chēng)樹(shù)H的一個(gè)新標(biāo)號(hào)：g(ai,j)=2n+h(ai,j). 由定理可知,f(E(T))=[1,2n-1],f(V(T))=[2n,4n-1].

圖4和圖5是解釋定理 2 的例子.

圖4 18個(gè)頂點(diǎn)連路樹(shù)的邊對(duì)稱(chēng)樹(shù)的全優(yōu)美標(biāo)號(hào)

圖5 32個(gè)頂點(diǎn)連路樹(shù)的邊對(duì)稱(chēng)樹(shù)的全優(yōu)美標(biāo)號(hào)

由定理 2 的證明可得到下面的推論：

[1]BloomGS,GolombSW.Applicationsofnumberedgraphs[J].ProceedingsoftheIEEE, 1997, (4): 562-570.

[2]GallianJA.Adynamicsurveyofgraphlabeling[J].TheElectronicJournalofCombinatorics, 2009, 12: 42-43.

[3]BondyJA,MurtyUSR.GraphTheorywithApplications[M].London:TheMacmillanPressLtd, 1976.

[4]PereiraJ,SinghT,ArumugamS.On(k,d)-Skolemgracefulgraphs[J].ElectronicNotesinDiscreteMathematics,2015,48:81-88.

[5]YaoB,ChengH,YaoM.Anoteonstronglygracefultrees[J].ArsCombinatoria, 2009, (92) :155-169.

[6]SubbiahSP,PandimadeviJ,ChithraR.Supertotalgracefulgraphs[J].ElectronicNotesinDiscreteMathematics,2015,48:301-304.

[7]ZhouX,YaoB,ChenX.Discussodd-gracefultreesconjecture[J].JournalofShandongUniversity(NaturalScience), 2012, (12): 31-36.

(責(zé)任編校：晴川)

Super Total Gracefulness on Path-linked Trees

ZHANG Mingjun

(School of Information Engineering, Lanzhou University of Finance and Economics,Lanzhou Gansu 730020, China)

The labeling theory of graphs is one of the technical means to study the nodes of computer networks. We present the concepts of trees including graceful tree, bipartite graceful tree, edge symmetric trees and super total graceful labelling. We define a class of path-linked tree T and prove that every path-linked tree T and its edge symmetric tree are super total graceful graph, so as to provide a reference for the development of computer networks.

bipartite graceful tree; graceful labelling; super total graceful labelling; edge symmetric tree

2017-01-31

國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào)：61662066、61363060)資助項(xiàng)目.

張明軍(1973— ), 男, 山東青州人, 蘭州財(cái)經(jīng)大學(xué)信息工程學(xué)院副教授, 碩士.研究方向：圖的標(biāo)號(hào)及復(fù)雜網(wǎng)絡(luò).

O

A

1008-4681(2017)02-0001-04