連路樹的全優美性

張明軍

(蘭州財經大學信息工程學院, 甘肅 蘭州 730020)

連路樹的全優美性

張明軍

(蘭州財經大學信息工程學院, 甘肅 蘭州 730020)

圖的標號理論是研究計算機網絡節點的技術手段之一.給出了優美樹、二分優美樹、邊對稱樹以及全優美標號的概念，定義了一類連路樹T，并證明了連路樹T及其邊對稱樹是全優美標號、全優美圖.為計算機網絡的發展提供參考.

二分優美樹；優美標號；全優美標號；邊對稱樹

1 準備知識

圖的標號理論是研究計算機網絡節點的技術手段之一.優美圖是圖的標號研究中十分重要的課題之一.優美圖在物流運輸、編碼理論、天文學等領域均有應用.圖的標號問題來自數學和圖論學科自身的問題, 甚至是編碼、晶體學中X-射線的二分性、通信網絡設計中的尋址、最佳電路布局和射電天文等應用領域[1,2]. 在優美樹猜想的研究中, 新的標號以及新的問題不斷涌現[3]. 本文討論了連路樹T及其邊對稱樹是全優美標號、全優美圖.

本文涉及的圖均為有限、無向、簡單圖. 文中沒有定義的術語和符號均采用文獻[3]. 本文中用記號[m,n]表示非負整數集{m,m+1,m+2,…,n}, 其中m和n均為整數; [k,l]e表示偶數集{k,k+2,k+4,…,l}, 其中k和l都是偶數, 且滿足0≤k

定義1[3,4].如果一棵n個頂點的樹T有一個正常標號f:V(T)→[0,n-1], 使得邊標號集合f(E(T))={f(uv)|uv∈E(T)}=[1,n-1], 則稱T為優美樹,f是T的一個優美標號.

定義2[5].設 (V1,V2) 是樹T的頂點集的二部劃分, 如果T有一個優美標號f, 使對樹T任意 2 個頂點x∈V1和y∈V, 總有f(x)

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

定義4[7].設T是一棵n階樹,T′ 是T的一個拷貝, 用一條邊e=xx′將T中的點與其拷貝的同構點相連, 得到的新樹稱為樹T的邊對稱樹.

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

2 主要結果及證明

定理1. 連路樹T有全優美標號, 是全優美圖.

證明 連路樹T有n=s(2m+1)個頂點. 下面給出樹T的標號函數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). 當s為偶數時, 有fmax(V1)

下面證明f是優美標號.

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

情形I: 主路上的邊標號與路Ps上的邊標號不相同.

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

路Ps上的邊標號為:

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]

當i≡1(mod2) 時, 若f(e1)=f(e2), 則一定有2m-j+1=0, 此時j=2m+1, 與j∈[0,2m]矛盾. 因此,f(e1)≠f(e2). 因為j+1≠0, 所以f(e1)≠f(e2) (i≡0(mod2)). 故主路上的邊標號與路Ps上的邊標號都不相同.

情形II: 主路Ps上的邊標號互不相同. 由于

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),即主路上的邊標號互不相同.

情形III: 同一條路Ps上的邊標號互不相同. 若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.

因為k≠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上的邊標號互不相同.

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

(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].

假設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) 中證明類似, 同理可得f(e1)≠f(e2).

(iii) 當i1≡1(mod2) 和i2≡0(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)|=|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

綜上所述, 所有邊標號中沒有相同的邊標號.即f(E(T))=[1,n-1].又fmax(V1)

因此, 連路樹T是二分優美樹.

(3)下面證明連路樹T有全優美標號, 是全優美圖.

連路樹T有n個頂點和n-1 條邊的二分優美樹, (V1,V2) 是它的頂點集的二部劃分,f是T的一個集有序優美標號. 給出連路樹T的一個新標號：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分別表示連路樹T的頂點數和邊數).又f(E(T))=[1,n-1], 所以, 連路樹T有全優美標號, 是全優美圖(STGG).

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

圖2 18個頂點連路樹的全優美標號

圖3 32個頂點連路樹的全優美標號

定理2.連路樹T的邊對稱樹是全優美標號, 全優美圖.

下面證明連路樹T的邊對稱樹H有全優美標號, 是全優美圖.

由上述證明可知連路樹T的邊對稱樹H是一個有2n個頂點和 2n-1條邊的二分優美樹.h是邊對稱樹H的一個集有序優美標號. 下面給出邊對稱樹H的一個新標號：g(ai,j)=2n+h(ai,j). 由定理可知,f(E(T))=[1,2n-1],f(V(T))=[2n,4n-1].

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

圖4 18個頂點連路樹的邊對稱樹的全優美標號

圖5 32個頂點連路樹的邊對稱樹的全優美標號

由定理 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.

(責任編校：晴川)

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

國家自然科學基金(批準號：61662066、61363060)資助項目.

張明軍(1973— ), 男, 山東青州人, 蘭州財經大學信息工程學院副教授, 碩士.研究方向：圖的標號及復雜網絡.

O

A

1008-4681(2017)02-0001-04