一致仙人掌樹(shù)的Felicitous性質(zhì)

楊思華，姚 兵，張婉佳

(西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，中國(guó)蘭州 730070)

1996年，Rosa［1］提出了一個(gè)猜想:每一棵樹(shù)都是優(yōu)美樹(shù).后來(lái)，Bermond［2］又提出了猜想:所有龍蝦樹(shù)都是優(yōu)美樹(shù).關(guān)于這兩個(gè)猜想已經(jīng)有了很多結(jié)果，但是一直沒(méi)有徹底地解決.Sin-Min Lee［3］等人于1991年提出了猜想:每一棵樹(shù)都是Felicitous樹(shù).該猜想與優(yōu)美樹(shù)猜想具有同等的理論價(jià)值，而且具有相同的難度，都是NP-hard問(wèn)題［4-12］.對(duì)于數(shù)學(xué)猜想的進(jìn)攻，導(dǎo)致圖的標(biāo)號(hào)迅速發(fā)展成為當(dāng)今圖論學(xué)科中十分活躍的分支，它在編碼理論、通訊網(wǎng)絡(luò)、物流等方面均有著重要應(yīng)用.

1 預(yù)備知識(shí)

本文涉及的圖均為有限、無(wú)向簡(jiǎn)單圖.文中沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均來(lái)自文獻(xiàn)［13］.為敘述簡(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ù)，且滿足0≤m ＜n;［k，l］e表示偶數(shù)集{k，k+2，k+4，…，l}，其中 k和 l為偶數(shù)，且滿足0≤k ＜l;［s，t］o表示奇數(shù)集{s，s+2，s+4，…，t}，其中 s和 t是滿足1≤s＜t的奇數(shù).

定義1 設(shè)G是(p，q)-圖，若存在一個(gè)單射f:V(G)→［0，q］，使得邊標(biāo)號(hào)集合{f(uv)|uv∈E(G)}=［0，q－1］，其中邊標(biāo)號(hào)為f(uv)=f(u)+f(v)(mod q)，那么稱G是Felicitous圖，并稱f是G的一個(gè)Felicitous標(biāo)號(hào).

對(duì)于定義1中的圖G和Felicitous標(biāo)號(hào)f，以下簡(jiǎn)記頂點(diǎn)標(biāo)號(hào)集合f(V(G))={f(u)|u∈V(G)}，邊標(biāo)號(hào)集合 f(E(G))={f(u)+f(v)|uv∈E(G)}，以及 f(E(G))(mod q)={f(uv)|uv∈E(G)}.

定義2 設(shè)(X，Y)是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，如果G有一個(gè)Felicitous標(biāo)號(hào)f，使得max{f(x)|x∈X}＜min{f(y)|y∈Y}(以下簡(jiǎn)記為f(X)＜f(Y))，則稱G是集有序Felicitous圖，也稱f是G的一個(gè)集有序Felicitous標(biāo)號(hào).

定義3 設(shè)G是(p，q)-圖，若存在一個(gè)單射f:V(G)→［0，q］，使得邊標(biāo)號(hào)集合{f(uv)|uv∈E(G)}=［1，q］，其中邊標(biāo)號(hào)為f(uv)=|f(u)－f(v)|，那么稱G是優(yōu)美圖，并稱f是G的一個(gè)優(yōu)美標(biāo)號(hào).進(jìn)一步，設(shè)(X，Y)是二部圖G的頂點(diǎn)集的一個(gè)二部劃分，若G有一個(gè)優(yōu)美標(biāo)號(hào)f，使得f(X)＜f(Y)，則稱G是集有序優(yōu)美圖，也稱f是G的一個(gè)集有序優(yōu)美標(biāo)號(hào).

定義 4 設(shè) H，T1，T2，…，Tn是樹(shù)，|H|=n，V(H)={ui|i∈［1，n］}，對(duì)每一個(gè) i∈［1，n］，將 H 的頂點(diǎn) ui和樹(shù)Ti中的一個(gè)頂點(diǎn)重合，得到的圖G叫做復(fù)合圖，特記為G=〈H;T1，T2，…，Tn〉.

定義5 若復(fù)合圖 G=〈H;T1，T2，…，Tn〉中的 H 是具有偶數(shù)個(gè)頂點(diǎn)的星 K1，n－1，且 Tk(k∈［1，n］)的頂點(diǎn)集二部劃分(Xk，Yk)滿足|Xk|=|Yk|=s，則稱 G=〈K1，n－1;T1，T2，…，Tn〉為一致仙人掌樹(shù).

由定義4可以看出復(fù)合圖指的同一類(lèi)圖，而定義5中的一致仙人掌樹(shù)是復(fù)合圖的一個(gè)特例.本文主要是利用較小的具有集有序Felicitous性質(zhì)的樹(shù)構(gòu)造較大的具有Felicitous性質(zhì)的一致仙人掌樹(shù)，并給出了集有序Felicitous樹(shù)與集有序優(yōu)美樹(shù)的等價(jià)關(guān)系.

2 主要結(jié)論及其證明

定理1 設(shè) T1，T2，…，Tn是集有序 Felicitous樹(shù)，每一棵樹(shù) Tk(k∈［1，n］)的頂點(diǎn)集二部劃分(Xk，Yk)滿足|Xk|=|Yk|=s，則一致仙人掌樹(shù) G=〈K1，n－1;T1，T2，…，Tn〉(n=2l，l∈N+)具有 Felicitous標(biāo)號(hào).

證 對(duì)k∈［1，n］，設(shè)集有序Felicitous樹(shù)Tk的頂點(diǎn)集二部劃分(Xk，Yk)滿足|Xk|=|Yk|=s，其中 Xk={uk，i|i∈［1，s］}和 Yk={vk，j|j∈［1，s］}.每一棵樹(shù) Tk(k∈［1，n］)具有集有序 Felicitous標(biāo)號(hào) fk.按照定義，fk滿足 max{fk(x)|x∈Xk}＜ min{fk(y)|y∈Yk}，不失一般性，fk(uk，i)=i－1，i∈［1，s］;fk(vk，j)=j+s－1，j∈［1，s］.設(shè)星 K1，n－1的頂點(diǎn)集二部劃分為(X，Y)，其中 X={x}，Y={y1，y2，…，yn－1}.

首先將星 K1，n－1中的頂點(diǎn) x 與 T1的頂點(diǎn) u1，1重合，再將 K1，n－1的頂點(diǎn) ya與 Ta+1中的頂點(diǎn) va+1，s(a∈［1，n－1］o)重合，最后將 K1，n－1的頂點(diǎn) yb與 Tb+1中頂點(diǎn) ub+1，1(b∈［1，n －1］e)重合，就得到本定理中的一致仙人掌樹(shù)G.

下面利用上述n個(gè)集有序Felicitous標(biāo)號(hào)fk(k∈［1，n］)給一致仙人掌樹(shù)G定義一個(gè)新標(biāo)號(hào)g如下:g(uk，i)=fk(uk，i)+(k －1)s，i∈［1，s］，k∈［1，n］;g(vk，j)=fk(vk，j)+(n+k － 2)s，j∈［1，s］，k∈［1，n］;將星K1，n－1與樹(shù) Tk(k∈［1，n］)重合的頂點(diǎn)標(biāo)號(hào)記為 g(x)=f1(u1，1)=0;g(ya)=fa+1(va+1，s)+(n+a －1)s=(n+a+1)s－1，a∈［1，n －1］0;g(yb)=fb+1(ub+1，1)+bs=bs，b∈［1，n －1］e.

令 T*=T1∪T2∪…∪Tn.不難驗(yàn)證 g(uk，i)∈［0，ns－1］，k∈［1，n］，i∈［1，s］;g(vk，j)∈［ns，2ns－1］，k∈［1，n］，j∈［1，s］.故有 g(V(T*))=［0，2ns－1］.再因?yàn)樾?K1，n－1的每個(gè)頂點(diǎn)與樹(shù) Tk(k∈［1，n］)中的頂點(diǎn)重合，所以 g(V(G))=g(V(T*))=［0，2ns－1］.由于|E(T*)|=n(2s－1)，|E(K1，n－1)|=n －1，故|E(G)|=|E(T*)|+|E(K1，n－1)|=2ns－1，即一致仙人掌樹(shù) G 有2ns－1 條邊.

下面計(jì)算 g(E(G))=g(E(T*))(mod 2ns－1)∪g(E(K1，n－1))(mod 2ns－1).首先給出 T*中邊 uk，ivk，j的標(biāo)號(hào)

其中 i∈［1，s］，j∈［1，s］以及 k∈［1，n］.由于 fk(uk，ivk，j)=fk(uk，i)+fk(vk，j)∈［s，3s－2］，因此

由(1)式導(dǎo)出 g(E(T*))=［ns，3ns－2］N*，其中

因?yàn)橐恢孪扇苏茦?shù) G 有2ns－1條邊，所以 g(E(T*))(mod 2ns－1)=［0，2ns－2］N*(mod 2ns－1)，且

下證 g(E(K1，n－1))(mod 2ns－1)=N*(mod 2ns－1).當(dāng)a∈［1，n －1］o時(shí)，邊xya滿足 g(xya)=g(x)+g(ya)=(a+n+1)s－1，從而

當(dāng) b∈［1，n －1］e時(shí)，邊 xyb滿足 g(xyb)=g(x)+g(yb)=bs，則有

結(jié)合(2)與(3)，得到 Sodd(mod 2ns－1)={(n+2)s－1，(n+4)s－1，…，(2n －2)s－1，0}，Seven(mod 2ns－1)=Seven，即

因此，g(E(G))=g(E(T*))(mod 2ns－1)∪g(E(K1，n－1))(mod 2ns－1)=［0，2ns－2］.

上面得到的 g(V(G))=［0，2ns－1］和 g(E(G))(mod 2ns－1)=［0，2ns－2］說(shuō)明 g 是一致仙人掌樹(shù) G=〈K1，n－1;T1，T2，…，Tn〉的一個(gè) Felicitous 標(biāo)號(hào).

注釋:圖1解釋定理1的一個(gè)例子.觀察一致仙人掌樹(shù)G=〈K1，9;T1，T2，…，T10〉，我們可看到樹(shù)T1與T10之間的邊(1，158)，(2，157)，(3，156)，(80，79)，(82，77)，(83，76)的每一條邊均可替代邊(0，159)，從而得到一棵新的具有Felicitous標(biāo)號(hào)的一致仙人掌樹(shù).不難發(fā)現(xiàn)，對(duì)其他樹(shù)Ts與T1(s∈［2，9］)之間的邊存在同樣的規(guī)律.定理1中的一致仙人掌樹(shù)G是不唯一的.

圖1 解釋定理1的一個(gè)例子Fig.1 An example for illustrating Theorem 1

定理2 一棵樹(shù)具有集有序Felicitous標(biāo)號(hào)的充分必要條件是它具有集有序優(yōu)美標(biāo)號(hào).

證 設(shè)具有 n個(gè)頂點(diǎn)的樹(shù) T的頂點(diǎn)集二部劃分為(X，Y)，這里 X={xi|i∈［1，s］}和Y={yj|j∈［1，t］}，s+t=n.

必要性 設(shè)樹(shù) T 有一個(gè)集有序 Felicitous標(biāo)號(hào) h，使得 h(xi)=i－1，i∈［1，s］;h(yj)=n － j，j∈［1，t］;以及 h(xiyj)=h(xi)+h(yj)(mod n－1).注意到 h(V(T))=［0，n－1］，h(E(T))=［0，n－2］，則利用 h作 T的另一個(gè)標(biāo)號(hào) α 如下:α(xi)=h(xi)，i∈［1，s］;α(yj)=h(yt－j+1)，j∈［1，t］;對(duì)邊 xiyj∈E(T)，有 α(xiyj)=|α(yj)－ α(xi)|=|h(yt－j+1)－h(huán)(xi)|.集有序 Felicitous標(biāo)號(hào) h，滿足 h(yj)∈h(xi)，所以 α(xiyj)=h(yt－j+1)－h(huán)(xi)=n －(t－j+1)－(i－1)=s+j－i.對(duì) i∈［1，s］和 j∈［1，t］，有 α(xiyj)∈［1，n －1］.由上可知，頂點(diǎn)標(biāo)號(hào)集合 α(V(T))=［0，n－1］，邊標(biāo)號(hào)集合 α(E(T))=［1，n－1］.所以，標(biāo)號(hào) α 是樹(shù) T的一個(gè)集有序優(yōu)美標(biāo)號(hào).

充分性 設(shè)樹(shù) T 有一個(gè)集有序優(yōu)美標(biāo)號(hào) f，使得 f(xi)=i－1，i∈［1，s］;f(yj)=s+j－1，j∈［1，t］;對(duì)邊xiyj∈E(T)，有 f(xiyj)=f(yj)－f(xi)=s+j－i.注意到 f(V(T))=［0，s+t－1］=［0，n －1］，f(E(T))=［1，n －1］.利用 f作 T 的另一個(gè)標(biāo)號(hào) g 如下:g(xi)=f(xi)，i∈［1，s］;g(yj)=f(yt－j+1)，j∈［1，t］;對(duì)邊 xiyj∈E(T)，有 g(xiyj)=g(xi)+g(yj)(mod n－1).易知，頂點(diǎn)標(biāo)號(hào)為 g(xi)∈［0，s－1］，g(yj)∈［s，n－1］.由于 g(xi)+g(yj)=f(xi)+f(yt－j+1)=n+i－ j－1，則對(duì) i∈［1，s］和 j∈［1，t］，有 g(xi)+g(yj)∈［n － t，n+s－2］，故邊標(biāo)號(hào) g(xiyj)(mod n－1)∈［0，n－2］.綜上，頂點(diǎn)標(biāo)號(hào)集號(hào) g(V(T))=［0，n－1］，邊標(biāo)號(hào)集合 g(E(T))(mod n－1)=［0，n－2］.所以，標(biāo)號(hào)g是樹(shù)T的一個(gè)集有序Felicitous標(biāo)號(hào).

［1］ROSA A.On certain valuations of the vertices of a graph［C］.New York:Theory of Graphs(Int Symp Rome，July 1966)，Gordon and Breach，1966:349-355.

［2］BERMOND J C.Graceful graphs，radio antennae and French windmills［M］.Pitman London:Graph Theory and Combinatorics，1979，34:18-37.

［3］LEE S M，SCHMEICHEL，SHEE S C.On felicitous graphs［J］.Discrete Math，1991，93:201-209.

［4］GALLIAN J A.A dynamic survey of graph labelling［J］.Electron J Combin，2011，18:#DS6.

［5］MANICKAM K，MARUDAI M，KALA R.Some results on felicitous labelling of graphs［J］.J Combin Math Combin Comput，2012，81:273-279.

［6］王 鴻，韓培友.兩類(lèi)大龍蝦幸福樹(shù)的構(gòu)造性證明［J］.鄭州大學(xué)學(xué)報(bào):自然科學(xué)版，2000，32(2):4-7.

［7］韓培友，姚 慧.兩大類(lèi)樹(shù)是幸福樹(shù)的新證法［J］.河南師范大學(xué)學(xué)報(bào):自然科學(xué)版，2001，29(1):20-26.

［8］何建鋒.一類(lèi)幸福樹(shù)的構(gòu)造性證明［J］.楚雄師范學(xué)院學(xué)報(bào)，2002，17(3):36-37.

［9］袁名焱，羅秋紅，湯自凱.由星補(bǔ)刻畫(huà)的一類(lèi)廣義線圖［J］.湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2012，35(1):5-8.

［10］王力工，樊穩(wěn)茹，張 政.多扇圖中保Wiener指數(shù)的樹(shù)［J］.湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2012，35(1):17-20.

［11］HAN P Y，CUI Z W.About the conjecture of felicitous trees［J］.Chin Quart J Math，2001，16(2):69-77.

［12］YAO B，CHENG H，YAO M，et al.A note on strongly graceful trees［J］.Ars Combinatoria，2009，92:155-169.

［13］BONDY J A，MURTY U S R.Graph theory with applications［M］.New York:MaCmillan Press Ltd，1976.