張明軍

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

一類蜘蛛樹(shù)的(k,d)-優(yōu)美標(biāo)號(hào)

張明軍

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

(k,d)-優(yōu)美標(biāo)號(hào)因?yàn)閰?shù)k,d可以取很多值，從而使得一些優(yōu)美圖是(k,d)-優(yōu)美標(biāo)號(hào)的特例.本文給出了(k,d)-優(yōu)美標(biāo)號(hào)的概念，定義了T(n+1,m)-蜘蛛樹(shù)，并證明了T(n+1,m)-蜘蛛樹(shù)不同情形下的(k,d)-優(yōu)美標(biāo)號(hào)．

(k,d)-優(yōu)美標(biāo)號(hào)；蜘蛛樹(shù)；邊標(biāo)號(hào)

隨著計(jì)算機(jī)的發(fā)展, 圖的標(biāo)號(hào)在網(wǎng)絡(luò)和通訊等領(lǐng)域中的應(yīng)用越來(lái)越廣泛[1-2], 而圖的各種標(biāo)號(hào)已發(fā)展到許多種[3-7], 其中(k,d)-優(yōu)美標(biāo)號(hào)因?yàn)閰?shù)k,d可以取很多值，從而使得一些優(yōu)美圖是(k,d)-優(yōu)美標(biāo)號(hào)的特例，所以研究(k,d)-優(yōu)美標(biāo)號(hào)就變得重要而有意義.本文討論了一類蜘蛛樹(shù)不同情形下的(k,d)-優(yōu)美標(biāo)號(hào).本文涉及的圖均為有限、無(wú)向、簡(jiǎn)單圖．文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均采用文獻(xiàn)[3]．為了敘述簡(jiǎn)便，記一個(gè)有p個(gè)頂點(diǎn)，q條邊的連通圖為(p,q)-圖.本文中用記號(hào)[m,n]表示非負(fù)整數(shù)集{m,m+1,m+2,…,n}, 其中m和n均為整數(shù).

對(duì)于一棵樹(shù)T，如果存在一個(gè)映射f:V[T]→[0,k] ，使對(duì)不同的頂點(diǎn)x,y∈V(T) ，有f(x)≠f(y) ，并且每條邊uv分配標(biāo)號(hào)f(uv)=|f(u)-f(v)| ，且使得邊標(biāo)號(hào)互不相同，則稱f是T的一個(gè)正常標(biāo)號(hào)．樹(shù)T的頂點(diǎn)、邊標(biāo)號(hào)分別記為f(V(T))={f(u)|u∈V(T)} 和f(E(T))={f(u)|uv∈E(G)}．如果樹(shù)T只有一個(gè)頂點(diǎn)ω滿足dT(ω)≥3，且對(duì)任意v∈V(T){ω}，有dT(v)≤2，那么這棵樹(shù)T稱為蜘蛛樹(shù)，頂點(diǎn)ω為蜘蛛樹(shù)T的中心.

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

定義2[2]設(shè)G是(p,q)-圖，若存在映射f:V(G)→[0,k+(q-1)d]，使得邊標(biāo)號(hào)集合f(E(G))={k,k+d,…,k+(q-1)d}，則稱f是G的一個(gè)(k,d)-優(yōu)美標(biāo)號(hào)．

下面給出本文的研究對(duì)象：以v0為頂點(diǎn)，有n+1條腿，且腿長(zhǎng)(除腿vv0)為m的蜘蛛樹(shù)稱為T(n+1,m)-蜘蛛樹(shù)， 如圖1所示.

圖1 T(n+1,m)-蜘蛛樹(shù)Fig.1 T(n+1,m)-spider tree

主要結(jié)果及證明如下：

定理1T(n+1,2)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)．

證明給出T(n+1,2)-蜘蛛樹(shù)的標(biāo)號(hào)：f(v)=0 ；f(v0)=k+2nd；f(vi,1)=id, (i=1,2,3,…,n)；f(vi,2)=k+(2i-1)d, (i=1,2,3,…,n)．

下面證明T(n+1,2)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)：

(1)由上面標(biāo)號(hào)可知f最大為f(v0)=k+2nd，最小為f(v)=0；所以f(V(T))=[0,k+2nd]．

(2)在T(n+1,2)-蜘蛛樹(shù)的邊標(biāo)號(hào)中沒(méi)有相同的標(biāo)號(hào).

f(v0v)=f(v0)-f(v)=k+2nd；

f(e1)=f(v0)-f(vi,1)=k+(2n-i)d；

f(e2)=f(vi,2)-f(vi,1)=k+(i-1)d.

下面分三種情形證明.

情形Ⅰ.T(n+1,2)-蜘蛛樹(shù)中沒(méi)有與腿v0v相同的邊標(biāo)號(hào).

因?yàn)閒(v0v)-f(e1)=id≠0 (i=1,2,…,n)；

f(v0v)-f(e2)=(2n-i+1)d≠0(i最大為n)，(i=1,2,…,n).

所以T(n+1,2)-蜘蛛樹(shù)中沒(méi)有與腿v0v相同的邊標(biāo)號(hào).

情形Ⅱ.T(n+1,2)-蜘蛛樹(shù)的同一條腿上沒(méi)有相同的邊標(biāo)號(hào).

因?yàn)閒(e1)-f(e2)=(2n-2i+1)d≠0(i最大為n)，(i=1,2,…,n).

所以T(n+1,2)-蜘蛛樹(shù)的同一條腿上沒(méi)有相同的邊標(biāo)號(hào).

情形Ⅲ.T(n+1,2)-蜘蛛樹(shù)的任意兩條不同腿上沒(méi)有相同的邊標(biāo)號(hào).

在T(n+1,2)-蜘蛛樹(shù)的不同腿上任取兩點(diǎn)i,j∈V(T)，(i,j=1,2,…,n;且i≠j)，則

|f(e1)-f(e2)|=|i-j|d≠0 (i≠j)；

或

|f(e1)-f(e2)|=|2n+1-i-j|d≠0 (i+j最大為2n)，(i,j=1,2,…,n).

即T(n+1,2)-蜘蛛樹(shù)的任意兩條不同腿上沒(méi)有相同的邊標(biāo)號(hào).

綜上所述,在T(n+1,2)-蜘蛛樹(shù)的邊標(biāo)號(hào)中沒(méi)有相同的標(biāo)號(hào), 即

f(E(T))={k,k+d,…,k+2nd}.

故T(n+1,2)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)．

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

圖2 T(3+1, 2)-蜘蛛樹(shù)Fig.2 (k-d) graceful labelling of T(3+1,2)-spider tree

圖3 T(6+1, 2)-蜘蛛樹(shù)的Fig.3 (k-d) graceful labelling of T(6+1,2)-spider tree

定理2T(n+1, 3)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)．

證明給出T(n+1,3)-蜘蛛樹(shù)的標(biāo)號(hào)：f(v)=0 ；f(v0)=k+3nd；

f(vi,1)=id, (i=1,2,3,…,n)；f(vi,2)=k+(n+2i-1)d, (i=1,2,3,…,n)．

f(vi,3)=(n+i)d, (i=1,2,3,…,n)

下面證明T(n+1,3)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)：

(1)由上面標(biāo)號(hào)可知f最大為f(v0)=k+3nd，最小為f(v)=0；所以f(V(T))=[0,k+3nd]．

(2)下面證明在T(n+1,3)-蜘蛛樹(shù)的邊標(biāo)號(hào)中沒(méi)有相同的邊標(biāo)號(hào).與定理1相同，本題也分三種情形證明.即

情形Ⅰ：T(n+1,3)-蜘蛛樹(shù)中沒(méi)有與腿v0v相同的邊標(biāo)號(hào)；

情形Ⅱ：T(n+1,3)-蜘蛛樹(shù)的同一條腿上沒(méi)有相同的邊標(biāo)號(hào).

情形Ⅲ.T(n+1,3)-蜘蛛樹(shù)的任意兩條不同腿上沒(méi)有相同的邊標(biāo)號(hào).(只證明情形Ⅲ)

在T(n+1,3)-蜘蛛樹(shù)的不同腿上任取兩點(diǎn)i,j∈V(T)，(i,j=1,2,…,n;且i≠j).

f(ei)=f(v0)-f(vi,1)=(3n-i)d

或f(ei)=f(vi,2)-f(vi,1)=k+(n+i-1)d

或f(ei)=f(vi,2)-f(vi,3)=k+id；

f(ej)=f(v0)-f(vj,1)=(3n-j)d

或f(ej)=f(vj,2)-f(vj,1)=k+(n+j-1)d

或f(ej)=f(vj,2)-f(vj,3)=k+jd.

則|f(ei)-f(ej)|=|i-j|d≠0 (i≠j)

或|f(ei)-f(ej)|=|k-(2n-i-j+1)d|≠0(i+j最大為2n)

或|f(ei)-f(ej)|=|k-(3n-i-j)d|≠0 (i+j最大為2n)， (i,j=1,2,…,n).

即T(n+1,3)-蜘蛛樹(shù)的任意兩條不同腿上沒(méi)有相同的邊標(biāo)號(hào).

綜上所述, 在T(n+1,3)-蜘蛛樹(shù)的邊標(biāo)號(hào)中沒(méi)有相同的標(biāo)號(hào), 即

f(E(T))={k,k+d,…,k+3nd}.

故T(n+1,3)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)．

圖4、圖5是解釋定理2的兩個(gè)例子

圖4 T(3+1, 3)-蜘蛛樹(shù)是(k,d)Fig.4 (k-d) graceful labelling of T(3+1,3)-spider tree

圖5 T(6+1,3)-蜘蛛樹(shù)Fig.5 (k-d) graceful labelling of T(6+1,3)-spider tree

定理3T(3+1,m)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)．

證明給出T(3+1,m)-蜘蛛樹(shù)的標(biāo)號(hào)：f(v)=0 ；f(v0)=3md；

f(v1,j)=(1.5j-0.5)d,(j=1(mod2))；

f(v1,j)=k+(3m-1.5j-2)d, (j=0(mod2))；

f(v2,j)=(1.5j+0.5)d, (j=1(mod2))；

f(v2,j)=k+(3m-1.5j)d, (j=0(mod2))；

f(v3,j)=(1.5j+1.5)d, (j=1(mod2))；

f(v3,j)=k+(3m-1.5j+2)d, (j=0(mod2)), (j=1,2,…,m).

(T(3+1,m)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)的證明與定理1、2類似，此處證明略)．

圖6、圖7是解釋定理3的兩個(gè)例子.

圖6 T(3+1, 6)-蜘蛛樹(shù)是(k,d)-優(yōu)美標(biāo)號(hào)Fig.6 (k-d) graceful labelling of T(3+1,6)-spider tree

圖7 T(3+1 , 9)-蜘蛛樹(shù)的邊對(duì)稱樹(shù)的強(qiáng)優(yōu)美標(biāo)號(hào)Fig.7 (k-d) graceful labelling of T(3+1,9)-spider tree

[1] BLOOM G S， GOLOMB S W. Applications of numbered graphs[J]. Proceedings of the IEEE, 1977,65(4):562-570.

[2] Gallian J A. A Dynamic Survey of Graph Labelling [J].The Electronic Journal of Combatorics , 2009,12:42-43.

[3]YAO B, CHENG H， YAO M. A Note on Strongly Graceful Trees[J]. Ars Combinatoria, 2009,92: 155-169.

[4]周向前，姚兵，陳祥恩.探討奇優(yōu)美樹(shù)猜想[J].山東大學(xué)學(xué)報(bào)(理學(xué)版)，2012(12):31-36.

[5]ZHOU X Q, YAO B，CHEN X E. Every Lobster Is Odd-elegant[J]. Information Processing Letters, 2013,113(1/2):30-33.

[6]姚明，姚兵，楊思華.關(guān)于樹(shù)的二分優(yōu)美標(biāo)號(hào)[J].蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版)，2014,50(6):875-880.

[7]張明軍，趙喜楊，姚兵.(2m+1,1)-p-樹(shù)的二分強(qiáng)優(yōu)美性和二分強(qiáng)奇優(yōu)美性[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2016,39(3):419-428.

(k,d)-gracefulnessofspidertree

ZHANG Ming-jun

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

(k,d)-graceful labeling’s parametersk,dcan be taken to a lot of values. It makes some graceful graphs is special cases of (k,d)-graceful labeling. This paper presented the concept of (k,d)-graceful labeling， definedT(n+1,m)-spider tree，and proved (k,d)-graceful labeling in different situations ofT(n+1,m)-spider.

(k,d)-graceful labelling; spider tree; edge label

2017-01-11

國(guó)家自然科學(xué)基金項(xiàng)目(61662066)；蘭州財(cái)經(jīng)大學(xué)高等教育教學(xué)改革研究重點(diǎn)項(xiàng)目(LJZ201707)；甘肅省高等學(xué)校科研項(xiàng)目(2017A-047)

張明軍，男，zhangmjlz@163.com

1672-6197(2018)01-0061-03

O157.5

A

(編輯：姚佳良)