趙喜楊, 姚 兵

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

探討樹的(k,d)-邊魔幻全標(biāo)號(hào)*

趙喜楊, 姚 兵

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

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

優(yōu)美標(biāo)號(hào); (k,d)-優(yōu)美標(biāo)號(hào); 邊魔幻全標(biāo)號(hào); (k,d)-邊魔幻全標(biāo)號(hào)

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

1 概 念

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

算法。下面給出本文要用到的幾個(gè)標(biāo)號(hào)定義。

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

以下頂點(diǎn)標(biāo)號(hào)集合{f(u) |u∈V(G)}簡(jiǎn)記為f(V(G)), 邊標(biāo)號(hào)集合{f(uv) |uv∈E(G)}簡(jiǎn)記為f(E(G))。

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

定義3[10]設(shè)G是(p,q)-圖。若存在常數(shù)λ和雙射f:V(G)∪E(G)→[1,p+q], 使對(duì)G的任意一條邊uv∈E, 總有f(u)+f(v)+f(uv)=λ, 則稱f為圖G的一個(gè)邊魔幻全標(biāo)號(hào),λ為魔幻常數(shù)。此外, 若G是具有頂點(diǎn)二部劃分(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], 使對(duì)G的任意一條邊uv∈E, 總有f(u)+f(v)+f(uv)=λ, 則稱f為圖G的一個(gè)(k,d)-邊魔幻全標(biāo)號(hào),λ為魔幻常數(shù)。此外, 若樹G是具有頂點(diǎn)二部劃分(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的一個(gè)(k,d)-超級(jí)集有序邊魔幻全標(biāo)號(hào)。

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

2 主要結(jié)論

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

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

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

對(duì)邊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è)標(biāo)號(hào)g如下：

對(duì)邊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。進(jìn)一步, 得到

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

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

所以, 標(biāo)號(hào)g是樹T的一個(gè)(k,d)-超級(jí)集有序邊魔幻全標(biāo)號(hào)。

充分性 設(shè)樹T有一個(gè)超級(jí)集有序邊魔幻全標(biāo)號(hào)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的一個(gè)標(biāo)號(hào)α如下：

α(xiyj)=h(xiyj)-nd

由于,

故

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

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

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

到的樹H具有(k,d)-超級(jí)集有序邊魔幻全標(biāo)號(hào)。

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

以及

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

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

(iv)對(duì)l∈[1,m-1],Tl與Tl+1之間的連邊xl+1, 1yl, 1的邊標(biāo)號(hào)為

l∈[1,m-1]

不難驗(yàn)證,

以及

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

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

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

注意到, 每一棵樹Hi有一個(gè)(k,d)-超級(jí)集有序邊魔幻全標(biāo)號(hào)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])的最大獨(dú)立集的頂點(diǎn)標(biāo)號(hào)均相同, 故可設(shè)樹H0有一個(gè)(k,d)-超級(jí)集有序邊魔幻全標(biāo)號(hào)g0, 使得

g0(u1)

gi(v2)< …

其中g(shù)0(ui)∈X0,g0(vj)∈Y0, 且(X0,Y0)為V(H0)的二部劃分。同時(shí)滿足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的一個(gè)標(biāo)號(hào)f′為：

接下來(lái), 按照p的奇偶性, 我們分別來(lái)找到對(duì)稱樹G*的一個(gè)標(biāo)號(hào)g。

(vi) 當(dāng)l∈[β+1, 2β]時(shí), 令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]；對(duì)邊ul, ivl, j∈E(G*), 令g(ul, ivl, j)=nd(2l-3)+g0(uivj)。

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

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

當(dāng)l∈[β+1, 2β],i∈[1,s]和j∈[1,t]時(shí),Hl的每一條邊ul, ivl, j滿足

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

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

5ndβ+2k-d=λ

因?yàn)? 當(dāng)l∈[1, 2β],i∈[1,s], 以及j∈[1,t]時(shí),g(ul, i)+g(ul, ivl, j)+g(vl, j)=λ。故,g是Hl(l∈[1, 2β])的一個(gè)使得g(ul, i)+g(ul, ivl, j)+g(vl, j)=λ的標(biāo)號(hào)。

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

考察對(duì)稱樹G*的邊wiwj的標(biāo)號(hào), 得到

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

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

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

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

(vii) 對(duì)每一條邊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) 對(duì)樹T的每一條邊wiwj,i∈[1,β],j∈[β+1, 2β], 有f′(wi)+f′(wiwj)+f′(wj)=λ。故當(dāng)p為偶數(shù)時(shí), 標(biāo)號(hào)g是對(duì)稱樹G*的(k,d)-超級(jí)集有序邊魔幻全標(biāo)號(hào)。

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

(x)當(dāng)l∈[β+2,2β+1]時(shí),令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]；對(duì)邊ul,ivl,j∈E(G*),令g(ul,ivl,j)=nd(2l-3)+g0(uivj)。

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

圖3和圖4中給出了說(shuō)明定理2的一個(gè)例子。

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

圖4 對(duì)稱樹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)美標(biāo)號(hào)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 54(5): 24-27.

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

[6] 吳躍生. 圖Fn, 4(r1,r2, …,r3n+1) 的交錯(cuò)標(biāo)號(hào)[J]. 中山大學(xué)學(xué)報(bào)(自然科學(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] 趙喜楊, 馬飛, 姚兵. 一類強(qiáng)優(yōu)美標(biāo)號(hào)樹[J]. 吉林大學(xué)學(xué)報(bào)(理學(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

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

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

O

A

0529-6579(2016)06-0067-07