探討樹的(k,d)-邊魔幻全標號*

趙喜楊, 姚 兵

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

探討樹的(k,d)-邊魔幻全標號*

趙喜楊, 姚 兵

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

研究了樹的(k,d)-集有序優(yōu)美標號和(k,d)-超級集有序邊魔幻全標號。通過連接頂點個數(shù)較小的(k,d)-集有序優(yōu)美樹的方式, 利用可算法化的構(gòu)造性證明可得到具有較大頂點數(shù)目的(k,d)-邊魔幻全標號的樹, 建立了(k,d)-集有序優(yōu)美標號和(k,d)-邊魔幻全標號之間的聯(lián)系。

優(yōu)美標號; (k,d)-優(yōu)美標號; 邊魔幻全標號; (k,d)-邊魔幻全標號

1963年,Ringel猜測：對預(yù)先給定的具有n+1個頂點的樹, 每一個2n+1個頂點的完全圖K2n+1可以被分解為2n+1棵樹, 使得這些樹均同構(gòu)于預(yù)先給定的樹。在研究Ringel猜想的過程中, Rosa發(fā)現(xiàn)：如果所有的樹都是優(yōu)美樹, 則Ring猜想成立。然而, Rosa的優(yōu)美樹猜想至今沒有被證明或否定, 使得這個猜想至今仍是一個吸引人的困難問題。對于數(shù)學(xué)猜想的進攻, 導(dǎo)致圖的著色和標號迅速發(fā)展成為當今圖論學(xué)科中十分活躍的分支, 圖的優(yōu)美標號也成為目前圖論研究的一個熱點問題[1-12], 他們在編碼理論、通訊網(wǎng)絡(luò)、物流等方面均有著重要的應(yīng)用。在此基礎(chǔ)上發(fā)展出了奇優(yōu)美標號、魔幻標號、幸福標號、(k,d)-優(yōu)美標號、(k,d)-邊魔幻全標號等十多種標號[7-13]。

1 概 念

記號[m,n]表示一個非負整數(shù)集{m,m+1,m+2, …,n}, 其中m和n均為整數(shù), 且滿足0≤m

算法。下面給出本文要用到的幾個標號定義。

定義1[10,12]對于給定的(p,q)-圖G, 如果存在一個單射f:V(G)→[0,q], 使得邊標號集合{f(uv)=|f(u)-f(v)|:uv∈E(G)}=[1,q], 則稱f是G的一個優(yōu)美標號, 也稱G為優(yōu)美圖。此外, 若G是具有頂點二部劃分(X,Y)的二分圖, 且f滿足max{f(x) |x∈X}

以下頂點標號集合{f(u) |u∈V(G)}簡記為f(V(G)), 邊標號集合{f(uv) |uv∈E(G)}簡記為f(E(G))。

定義2[10,12]如果(p,q)-圖G有一個映射f:V(G)→[0,k+(q-1)d],使得G的任何2個頂點x,y滿足f(x)≠f(y), 且定義每條邊uv的標號為f(uv)=|f(u)-f(v)|, 當f(E(G))={f(uv) |uv∈E(G)}={k,k+d,k+2d, …,k+(q-1)d} (k,d≥1)時, 則稱f是(p,q)-圖G的一個(k,d)-優(yōu)美標號, 也稱G為(k,d)-優(yōu)美圖。此外, 若G是具有頂點二部劃分(X,Y)的偶圖, 且f滿足max{f(x) |x∈X}

定義3[10]設(shè)G是(p,q)-圖。若存在常數(shù)λ和雙射f:V(G)∪E(G)→[1,p+q], 使對G的任意一條邊uv∈E, 總有f(u)+f(v)+f(uv)=λ, 則稱f為圖G的一個邊魔幻全標號,λ為魔幻常數(shù)。此外, 若G是具有頂點二部劃分(X,Y)的偶圖, 且f滿足f(X∪Y)=[1,p]和max{f(x) |x∈X}

定義4[10]設(shè)G是(p,q)-圖。若存在常數(shù)λ和雙射f:V(G)∪E(G)→{d, 2d, …,μd,k+(μ+1)d,k+(p+q-1)d},μ∈[1,p+q-1], 使對G的任意一條邊uv∈E, 總有f(u)+f(v)+f(uv)=λ, 則稱f為圖G的一個(k,d)-邊魔幻全標號,λ為魔幻常數(shù)。此外, 若樹G是具有頂點二部劃分(X,Y)的偶圖, 且f滿足f(X)={d, 2d, …, |X|d},f(Y)={k+|X|d,k+(|X|+1)d, …,k+(|X|+|Y|-1)d}, 則稱f是G的一個(k,d)-超級集有序邊魔幻全標號。

定義 5 設(shè)H1,H2, …,H|V(T)|和T是樹,V(T)={ui|i∈[1, |V(T)|]}。對每一個i∈[1, |V(T)|], 將T的一個頂點ui與樹Hi中的一個頂點重合, 得到的圖G叫做復(fù)合圖, 記為G=。若|V(H1)|=|V(H2)|= …=|V(H|V(T)|)|, 則稱G為對稱樹。若V(H1)=V(H2)= …=V(H|V(T)|), 則稱G為一致對稱樹, 特記作(T,H)。

2 主要結(jié)論

引理1 一棵樹是(k,d)-集有序優(yōu)美的充要條件是它具有(k,d)-超級集有序邊魔幻全標號。

證明 設(shè)n個頂點的樹T的頂點集二部劃分為(X,Y), 這里X={xi|i∈[1,s]} 和Y={yi|i∈[1,t]},s+t=n。

必要性 設(shè)樹T有一個(k,d)-集有序優(yōu)美標號f, 使得

對邊xiyj∈E(T), 有

f(xiyj)=f(yj)-f(xi)=k+(s+j-i-1)d

注意到,f(V(T))=[0, (s-1)d]d∪[k+(s-1)d,k+(n-2)d]d和f(E(T))=[k,k+(n-2)d]d。利用f作T的另一個標號g如下：

對邊xiyj∈E(T), 令g(xiyj)=nd+f(xiyj)

易知g(xi)∈[d,sd]d,g(yj)∈[k+sd,k+(s+t-1)d]d和g(xiyj)∈[nd+k,k+(2n-2)d]d。進一步, 得到

id+nd+k+(s+j-i-1)d+k+

(s+t-j+1-2)d+d=2k+ (2n+s-1)d

所以, 標號g是樹T的一個(k,d)-超級集有序邊魔幻全標號。

充分性 設(shè)樹T有一個超級集有序邊魔幻全標號h, 使得h(xi)=id,i∈[1,s],h(yj)=k+(n-j)d,j∈[1,t], 以及h(xiyj)=k+(2n-t-j-i-1)d。注意到h(V(T))=[d,sd]d∪[k+sd,k+(s+t-1)d]d,h(E(T))=[nd+k,k+(2n-2)d]d, 且h(xi)+h(xiyj)+h(yj)=2k+(3n-t-1)d。利用h作T的一個標號α如下：

α(xiyj)=h(xiyj)-nd

由于,

故

以上論證說明, 標號α是樹T的一個(k,d)-集有序優(yōu)美標號, 如圖1所示。

定理1T1,T2, …,Tm為 (k,d)-集有序優(yōu)美樹。則存在頂點ui∈V(Ti) (i∈[1,m]), 使得用邊連接頂點uj與頂點uj+1(j∈[1,m-1])后得

圖1 (k,d)-集有序優(yōu)美標號和 (k,d)-超級集有序邊魔幻全標號Fig.1 A set-ordered (k,d)-graceful labelling, and a super set-ordered (k,d)-edge magic total labelling

到的樹H具有(k,d)-超級集有序邊魔幻全標號。

證明 對l∈[1,m], 設(shè)Tl是nl個頂點的(k,d)-集有序優(yōu)美樹, 其頂點集合二部劃分(Xl,Yl)滿足Xl={xl, i|i∈[1,sl]}和Yl={yl, j|j∈[1,tl]}, 這里sl+tl=nl。由引理1, 樹Tl(l∈[1,m])有一個(k,d)-超級集有序邊魔幻全標號gl, 使當i∈[1,sl]和j∈[1,tl], 有

以及

2l+(2nl+sl-1)d

對l∈[1,m-1], 用邊將樹Tl的頂點yl, 1與樹Tl+1的頂點xl+1, 1連接在一起, 就得到本定理所要求的樹H。利用上述m個超級集有序邊魔幻全標號gl(l∈[1,m]), 給樹H定義一個標號g如下：

(iv)對l∈[1,m-1],Tl與Tl+1之間的連邊xl+1, 1yl, 1的邊標號為

l∈[1,m-1]

不難驗證,

以及

對邊xl+1, 1yl, 1∈E(H),l∈[1,m-1], 有

觀察圖2中的例子, 不難發(fā)現(xiàn), 有多種方法可以將樹T1,T2, …,Tm“串聯(lián)”在一起, 從而構(gòu)成較大規(guī)模的具有(k,d)-超級集有序邊魔幻全標號的樹。

圖2 解釋定理1的例子, 其中樹H的一個(k,d)-超級集有序邊魔幻全標號Fig.2 A super (k,d)-edge magic total labelling of the tree H for illustrating Theorem 1

注意到, 每一棵樹Hi有一個(k,d)-超級集有序邊魔幻全標號gi, 使得

其中g(shù)i(ui)∈Xi,gi(vj)∈Yi, (Xi,Yi) 為V(Hi)的二部劃分。顯然有

以及gi(ui)+gi(uivj)+gi(vj)=2k+(2ni+si-1)d,i∈[1,p]

根據(jù)定理的假設(shè), 所有樹Hi(i∈[1,p])的最大獨立集的頂點標號均相同, 故可設(shè)樹H0有一個(k,d)-超級集有序邊魔幻全標號g0, 使得

g0(u1)

gi(v2)< …

其中g(shù)0(ui)∈X0,g0(vj)∈Y0, 且(X0,Y0)為V(H0)的二部劃分。同時滿足g0(ui)=gl(ui),g0(vj)=gl(vj)i∈[1,s],j∈[1,t],l∈[1,p]。顯然,g0(V(H0))=[d,sid]d∪[k+sid,k+(n-1)d]d,g0(E(H0))=[k+nd,k+2(n-2)d]d, 以及

2k+(2n+s-1)d

利用f定義T的一個標號f′為：

接下來, 按照p的奇偶性, 我們分別來找到對稱樹G*的一個標號g。

(vi) 當l∈[β+1, 2β]時, 令g(ul, i)=k+nd(3β+1-l)+g0(ui)-(s+1)d,i∈[1,s]；g(vl, j)=nd(2β-l)+g0(vj)-k+d,j∈[1,t]；對邊ul, ivl, j∈E(G*), 令g(ul, ivl, j)=nd(2l-3)+g0(uivj)。

下面證明標號g是樹G*的(k,d)-超級集有序邊魔幻全標號。當l∈[1,β],i∈[1,s]和j∈[1,t]時,Hl的每一條邊ul, ivl, j滿足

[2k+(2n+s-1)d]=5ndβ+2k-d=λ

當l∈[β+1, 2β],i∈[1,s]和j∈[1,t]時,Hl的每一條邊ul, ivl, j滿足

k+d+nd(2l-3)+g0(uivj)=

nd(3β+1-l+2l-1+2β-l)-d+2k=

5ndβ+2k-d=λ

因為, 當l∈[1, 2β],i∈[1,s], 以及j∈[1,t]時,g(ul, i)+g(ul, ivl, j)+g(vl, j)=λ。故,g是Hl(l∈[1, 2β])的一個使得g(ul, i)+g(ul, ivl, j)+g(vl, j)=λ的標號。

不難發(fā)現(xiàn), 樹T和樹H的重合頂點具有任意性。對于樹T和樹Hi(i∈[1,p])的重合頂點來說, 當Hl的頂點ul, i與樹T的頂點wl重合時, 用g(ul, i)來替換f′(wl)；Hp-l的頂點up-l, s+1-i與樹T的頂點wp-l重合時(l∈[1,β]), 用g(up-l, i)來替換f′(wp-l,i)(i∈[1,s]), 然后定義g(wiwj)=f′(wiwj),wiwj∈E(T)。另一方面, 當l∈[1,β], 樹Hl的頂點vl, j與樹T的頂點wl重合時, 用g(vl, j)來替換f′(wl),Hp-l的頂點vp-l, t+1-j與樹T的頂點wp-l重合時, 用g(vp-l, j)來替換f((wp-l, j),j∈[1,t]；最后定義g(wiwj)=f((wiwj),wiwj∈E(T)。至此, 對稱樹G*的標號g已經(jīng)全部給出。

考察對稱樹G*的邊wiwj的標號, 得到

nd(i+j-i+5β-j)+2k-d=

sd+k+(s+t-l)d=

綜合上述推理, 可知對稱樹G*的頂點二部劃分(X*,Y*)滿足g(X*)

邊標號集合g(E(G*))=[k+2ndβ,k+4ndβ-1]。此時，已經(jīng)得到：

(vii) 對每一條邊ul, ivl, j∈E(G*),l∈[1, 2β+1],i∈[1,s],j∈[1,t], 有g(shù)(ul, i)+g(ul, ivl, j)+g(vl, j)=λ；

(viii) 對樹T的每一條邊wiwj,i∈[1,β],j∈[β+1, 2β], 有f′(wi)+f′(wiwj)+f′(wj)=λ。故當p為偶數(shù)時, 標號g是對稱樹G*的(k,d)-超級集有序邊魔幻全標號。

(ix) 當l∈[1,β+1]時, 令g(ul, i)=nd(l-1)+g0(ui),i∈[1,s]；g(vl, j)=nd(β+l-1)+g0(vj),j∈[1,t]；對邊ul, ivl, j∈E(G*), 令g(ul, ivl, j)=2nd(2β+1-l)+g0(uivj)。

(x)當l∈[β+2,2β+1]時,令g(ul,i)=k+nd(3β+2-l)-d+g0(ui),i∈[1,s]；g(vl,j)=nd(2β+1-l)+d+g0(vj)(k,j∈[1,t]；對邊ul,ivl,j∈E(G*),令g(ul,ivl,j)=nd(2l-3)+g0(uivj)。

證明的其余部分完全類似于情形1,故不再贅述。綜合情形1和情形2的論證, 定理得證。

圖3和圖4中給出了說明定理2的一個例子。

圖3 (k,d)-優(yōu)美樹H1, …, H7和集有序優(yōu)美樹TFig.3 (k,d)-graceful trees H1, …, H7 and set-ordered graceful tree T

圖4 對稱樹Fig.4 A symmetric tree

[1]ZHOUXQ,YAOB,CHENXE.Everylobsterisodd-elegant[J].InformationProcessingLetters, 2013, 113(1/2): 30-33.

[2]GALLIANJA.Adynamicsurveyofgraphlabeling[J/OL].TheElectronicJournalofCombinatorics, 2015,DS6.http:∥www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS6/pdf.

[3]BACAM,BERTAULTF,MACDOUGALLJA,etal.Vertex-antimagictotallabelingsofgraphs[J].Discuss.MathGraphTheory, 2003, 23(1): 67-83.

[4] 唐保祥, 任韓. 2類優(yōu)美圖的冠的優(yōu)美標號[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2015, 54(5): 24-27.

[5] 魏麗俠, 張坤龍. 幾類并圖的優(yōu)美性[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2008, 47(3): 10-13.

[6] 吳躍生. 圖Fn, 4(r1,r2, …,r3n+1) 的交錯標號[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2016, 55(4): 11-14.

[7] YAO B, CHENG H, YAO M, et al. A note on strongly graceful trees [J]. Ars Combinatoria, 2009, 92: 155-169.

[8] ZHOU X Q, YAO B, CHEN X E, et al. A proof to the odd-gracefulness of all lobsters [J]. Ars Combinatoria, 2012, 103: 13-18.

[9] WANG H Y, YAO B, YAO M. Generalized edge-magic total labellings of models from reseaching networks [J]. Information Sciences, 2014, 279: 460-467. DOI:10.1016/j.ins.2014.03.132.

[10] WANG H Y, YAO B, YANG C, et al. Edge-magic total labellings of some network models [J]. Applied Mechanics and Materials, 2013, 347-350: 2752-2757. DOI:10.4028/www.scientific. net/AMM.347-350.2752.

[11] WANG H Y, YAO B, YANG C, et al. Labelling properties of models related with complex networks based on constructible structures [J]. Advanced Materials Research, 2013(765/766/767): 1118-1123.DOI：10. 4028/www.scientific.net/AMR.765/766/767.1118.

[12] 趙喜楊, 馬飛, 姚兵. 一類強優(yōu)美標號樹[J]. 吉林大學(xué)學(xué)報(理學(xué)版), 2016, 54(2): 222-228.

Probing (k,d)-edge magic total labellings of trees

ZHAOXiyang,YAOBing

(College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China)

The (k,d)-edgemagicpropertyoftreesisstudied.Byusingtheconnectionbetween(k,d)-gracefullabellingsand(k,d)-edgemagictotallabellingsforgeneratinglargeclassesof(k,d)-edgemagictotaltreesfromsmallergracefultrees,therelationshipbetween(k,d)-gracefullabellingsand(k,d)-edgemagiclabellingsisestablished.

graceful labellings; (k,d)-gracefullabellings;edgemagictotallabelling; (k,d)-edgemagictotallabelling

10.13471/j.cnki.acta.snus.2016.06.010

2016-01-11

國家自然科學(xué)基金資助項目 (61163054，61363060，61662066)

趙喜楊 (1990年生)，女；研究方向：圖的標號及染色；通訊作者：姚兵;E-mail:yybb918@163.com

O

A

0529-6579(2016)06-0067-07