張明軍

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

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

張明軍

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

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

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

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

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

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

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

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

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

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

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

證明給出T(n+1,2)-蜘蛛樹的標(biā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)-蜘蛛樹是(k,d)-優(yōu)美標(biāo)號：

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

(2)在T(n+1,2)-蜘蛛樹的邊標(biāo)號中沒有相同的標(biā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)-蜘蛛樹中沒有與腿v0v相同的邊標(biā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)-蜘蛛樹中沒有與腿v0v相同的邊標(biāo)號.

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

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

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

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

在T(n+1,2)-蜘蛛樹的不同腿上任取兩點(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)-蜘蛛樹的任意兩條不同腿上沒有相同的邊標(biāo)號.

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

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

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

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

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

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

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

證明給出T(n+1,3)-蜘蛛樹的標(biā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)-蜘蛛樹是(k,d)-優(yōu)美標(biāo)號：

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

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

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

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

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

在T(n+1,3)-蜘蛛樹的不同腿上任取兩點(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)-蜘蛛樹的任意兩條不同腿上沒有相同的邊標(biāo)號.

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

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

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

圖4、圖5是解釋定理2的兩個例子

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

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

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

證明給出T(3+1,m)-蜘蛛樹的標(biā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)-蜘蛛樹是(k,d)-優(yōu)美標(biāo)號的證明與定理1、2類似，此處證明略)．

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

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

圖7 T(3+1 , 9)-蜘蛛樹的邊對稱樹的強(qiáng)優(yōu)美標(biā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)美樹猜想[J].山東大學(xué)學(xué)報(理學(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)于樹的二分優(yōu)美標(biāo)號[J].蘭州大學(xué)學(xué)報(自然科學(xué)版)，2014,50(6):875-880.

[7]張明軍，趙喜楊，姚兵.(2m+1,1)-p-樹的二分強(qiáng)優(yōu)美性和二分強(qiáng)奇優(yōu)美性[J].應(yīng)用數(shù)學(xué)學(xué)報,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

國家自然科學(xué)基金項(xiàng)目(61662066)；蘭州財經(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

(編輯：姚佳良)