探討斐波納契毛毛蟲樹的邊標號

劉信生，王蓓蓓，陳 璟,姚 兵

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

?

·數(shù)理科學·

探討斐波納契毛毛蟲樹的邊標號

劉信生，王蓓蓓，陳 璟,姚 兵

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

為了探討斐波納契毛毛蟲樹的邊標號,采用不同于原定義的圖標號的方法-先從邊對每個圖進行標號。利用先從邊標號的特點,主要討論了1-斐波納契毛毛蟲樹的邊二分奇優(yōu)美標號,邊優(yōu)美標號及邊魔幻全標號。最后討論了1-斐波納契毛毛蟲超級同構(gòu)圖的二分奇優(yōu)美標號。這樣的方法省去了大量繁復工作,大大提高了圖標號的效率。

1-斐波納契毛毛蟲樹;邊標號;二分奇優(yōu)美標號;邊優(yōu)美標號;邊魔幻全標號;超級同構(gòu)圖

1966年,Rosa[1]提出了一個猜想:每一棵樹都是優(yōu)美樹。關(guān)于這個猜想已經(jīng)有了很多的結(jié)果,但是一直沒有徹底的解決,進而使得優(yōu)美樹猜想至今仍是一個吸引人的困難問題。對于數(shù)學猜想的進攻,導致圖的著色和標號迅速發(fā)展成為當今圖論學科中十分活躍的分支,它們在編碼理論、通訊網(wǎng)絡、物流等方面均有著重要的應用[2-7]。

文中所提到的圖都是簡單的、無向的并且是有限的,沒有定義的術(shù)語和符號均采自于文獻[8]。為敘述簡便,我們把一個有p個頂點和q條邊的圖叫做 (p,q)-圖。用V(G)和E(G)分別表示樹G的頂點個數(shù)和邊數(shù)目。設一個(p,q)-圖G有一個映射f:V(G)→[0,q],記f (V(G))={f (u): u∈V(G)},f (E(G))=f (uv)={|f (u)-f (v)|: uv∈E(G)}。此外,設G是具有頂點二部劃分(X,Y)的二分圖,若對任意的x∈X和y∈Y,標號f滿足f(x)

本文的標號定義相反于一般的圖標號。即對一個有n個頂點的圖G,存在一個映射 f: E(G)→[1, n-1],然后確定圖G的頂點標號,使其滿足特定的條件,這是本文的創(chuàng)新之處。我們發(fā)現(xiàn),一旦圖G的所有邊的標號確定了,接下來只需確定圖中一個頂點的標號,那么圖G的其余頂點的標號就可以被確定了下來。就像多米諾骨牌一樣,只需給出第一個頂點的標號,其余頂點的標號就一個接一個地確定下來。

定義1[9-10]樹G的一個頂點標號L是指從V (G)到{0,1,…,2|E|-1},且當頂點u, v不同時,有L(u)≠L(v)。對G的邊e=uv,定義L′ (e)=|L(u)-L(v)|為邊uv的邊標號,當 E(G)的主軸標號為{1,3,…,2|E|-1},則說L為簡單圖G的奇優(yōu)美標號,稱G為奇優(yōu)美圖。

定義2[11-12]對于給定的(p, q)-圖G,如果存在一個映射 f: V→[0,2q-1],使得 f (V(G))=p和 f (E(G))={1,3,5,…,2q-1},則稱G是奇優(yōu)美圖,稱f是G的一個奇優(yōu)美標號。此外,若G是具有頂點二部劃分(X, Y)的二分圖,且f滿足 f (X)

定義3[13]對于給定的(p, q)-圖G,如果存在一個映射f: V(G)→[0, q],使得 f(E(G))=[1, q],則稱f是G的一個優(yōu)美標號,也稱G是優(yōu)美圖。

定義4[14-15]設G是(p, q)-圖,若存在常數(shù)λ和雙射f: V(G)∪E(G)→[1, p+q],使對G的任意一條邊 uv∈E,總有f (u)+f (v)+f (uv)=λ,則稱f為圖G的一個邊魔幻全標號。

定義5 設G是(p, q)-圖,若存在一個映射f滿足f: E(G)→[1,q],然后f: V(G)→[0, q],使得f (u)≠f (v), |f (u)-f (v)|=f (uv)。則稱f為圖G的邊優(yōu)美映射,G為邊優(yōu)美的。

設 p=a0a1a2…an為一條路,對i={1,2,…,n},給ai連接一度點ai,1,ai,2,…,ai,mi所得到的圖稱為毛毛蟲樹,記為T。如果m1=1,m2=1,且mi=mi-2+mi-1對i≥2 成立,則稱T為1-斐波納契毛毛蟲樹,特記為F(n)。給任意個1-斐波納契毛毛蟲樹對應位置的對應頂點之間加一條關(guān)聯(lián)邊所構(gòu)成的圖稱為1-斐波納契超級同構(gòu)圖。

1 主要結(jié)論

定理1 每一棵1-斐波納契毛毛蟲樹都有一個邊奇優(yōu)美標號,且它是二分奇優(yōu)美標號。

證 明 設 F(n) 為一棵1-斐波納契毛毛蟲樹。定義F(n)的一個標號f如下,先給 F(n)的邊標號:

f (anan, j)=2q-1-2(mn-j), j∈{1,2,…,mn};

f (an-1an)=2q-1-2mn;

f (an-1an-1, j)=f (an-1an)-2(mn-1-j+1), j∈{1,2,…,mn-1};

f (an-2an-1)=f (an-1an-1)-2，

f (an-2an-2, j)=f(an-2an-1)-2(mn-2-j+1), j∈{1,2,…,mn-2};

f (an-3an-2)=f(an-2an-2,1)-2。

一般地,f (akak, j)=f (akak+1)-2(mkj+1), j∈{1,2,…,mk}; f (akak+1)=f (ak+1ak+1,1)-2，其中mi=mi-2+mi-1。

由以上定義的邊標號f可知,當j=mn時,可f(anan,mn)=2q-1=2|E(F(n))-1|為F(n)中邊標號的最大值且為奇數(shù)。又因為F(n)為(p, q)-圖,含q條邊,且集合{1,3,5,…,2q-1}中元素個數(shù)為2q-1,則定義的F(n)的邊標號f滿足f (E(F(n)))={1,3,5,…,2|E(F(n))-1|}。至此,F(n)的所有邊標號完畢。下面給 F(n)的頂點標號如下:

f (an)=0, f (an, j)=2q-1-2(mn-j), j∈{1,2,…,mn};

f (an-1)=f (an,1)-2,

f (an-1, j)=f (an)+2(mn-1-j+1), j∈{1,2,…,mn-1};

f (an-2)=f (an-1,1)+2, f (an-2, j)=

f (an-1)-2(mn-2-j+1), j∈{1,2,…,mn-2};

f (an-3)=f (an-2,1)-2, f (an-3, j)=

f (an-2)+2(mn-3-j+1), j∈{1,2,…,mn-3};

f (an-4)=f (an-3,1)+2, f (an-4, j)=

f (an-3)-2(mn-4-j+1), j∈{1,2,…,mn-4};

一般地,當f (ak)=f (ak+1,1)-2 時,f (ak, j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk};當f (ak)=f (ak+1,1)+2時,f (ak, j)=f (ak+1)-2(mk-j+1), j∈{1,2,…,mk};在式 f (ak)=f (ak+1,1)-2 和 f (ak, j)=f (ak+1)-2(mk-j+1), j∈{1,2,…,mk}式下被標號的所有點均為奇數(shù)點,把它們所構(gòu)成的集合記為Y。在式f (ak)=f (ak+1,1)+2, f (ak,j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk}下被標號的所有點均為偶數(shù)點,把它們所構(gòu)成的集合記為X。

這樣,F(n)的頂點集的二部劃分為(X, Y),其中X表示標號數(shù)為偶數(shù)的點,Y表示標號數(shù)為奇數(shù)的點。每次所標的偶數(shù)點值是從0 開始依次遞增的,每次所標的奇數(shù)點值是從2q-1開始依次遞減的,又因為F(n)為(p, q)-圖且邊標號的最大值為2q-1,所以綜上可得 f (X)

圖1例舉一個二分奇優(yōu)美斐波納契毛毛蟲樹例子。

圖1 1-斐波納契毛毛蟲樹F(6) 的二分奇優(yōu)美標號Fig.1 The bipartite odd-graceful labelling of 1-Fibonacci′s caterpillar tree F(6)

定理2 所有的1-斐波納契毛毛蟲樹都有邊優(yōu)美標號。

證 明 設F(n) 為一棵1-斐波納契毛毛蟲樹,定F(n)的一個標號f如下:先給F(n) 的邊標號:

f (anan, j)=q-(mn-j), j∈{1,2,…,mn};

f (an-1an)=f (anan,1)-1, f (an-1an-1, j)=f (an-1an)-(mn-1-j+1), j∈{1,2,…,mn-1};

f (an-2an-1)=f (an-1an-1, j)-1;

f (an-2an-2, j)=f (an-2an-1)-(mn-2-j+1), j∈{1,2,…,mn-2}。

一般地,f (akak, j)=f (akak+1)-(mk-j+1), j∈{1,2,…,mk}; f (akak+1)=f (ak+1ak+1,1)-1其中mi=mi-2+mi-1。

由以上定義的邊標號f可知,當j=mn時,可f(anan,mn)=q為F(n)中邊標號的最大值。又因為F(n)為(p, q)-圖,含q條邊,且集合{1, 3, 5,…,q}中元素個數(shù)為q,則定義的F(n)的邊標號f 滿足f (E(F(n)))={1, 3, 5,…,q}。至此,F(n)的所有邊標號完畢。下面給F(n)的頂點標號如下:

f (an)=0, f (an, j)=q-(mn-j), j∈{1,2,…,mn};

f (an-1)=f (an,1)-1, f (an-1, j)=

f (an)+(mn-1-j+1), j∈{1,2,…,mn-1};

f (an-2)=f (an-1,1)+1, f (an-2, j)=

f (an-1)-(mn-2-j+1), j∈{1,2,…,mn-2};

f (an-3)=f (an-2,1)-1, f (an-3, j)=

f (an-2)+(mn-3-j+1), j∈{1,2,…,mn-3};

一般地,當f (ak)=f (ak+1,1)-1 時,f (ak, j)=f (ak+1)+(mkj+1), j∈{1,2,…,mk}; 其中mi=mi-2+mi-1。當f (ak)=f (ak+1,1)+1時,

f (ak, j)=f (ak+1)-(mk-j+1), j∈{1,2,…,mk}; 其中mi=mi-2+mi-1。由以上定義的F(n)的一個標號f知邊標號的最大值q對應于點標號的最小值 0,從而可得f (V(F(n)))→[0, q]。

由優(yōu)美標號的定義,可得f為1-斐波納契毛毛蟲樹的優(yōu)美標號。所以1-斐波納契毛毛蟲樹都是優(yōu)美樹。

圖2例舉一個優(yōu)美斐波納契毛毛蟲樹的例子。

圖2 1-斐波納契毛毛蟲樹F(7)的優(yōu)美標號Fig.2 The graceful labelling of 1-Fibonacci′s caterpillar tree F(7)

定理3 任何一棵1-斐波納契毛毛蟲樹都有一個邊標號,且它是邊魔幻全標號。

在中國發(fā)展西洋歌劇，就必須面對許多的現(xiàn)實問題，由于中國的歷史文化的源遠流長，深入人心必然會影響西方歌劇在中國的傳播。從這個方面來說，延安秧歌劇發(fā)展對我國認識西方歌劇有著很好的過渡意義，也對我國創(chuàng)作第一部民族歌劇《白毛女》有著先導作用。

證 明 定義1-斐波納契毛毛蟲樹F(n)的一個標號 f 如下,先對F(n)的邊標號:

f(anan, j)=q-(mn-j), j∈{1,2,…,mn};

f (an-1an)=f (anan,1)-1; f (an-1an-1, j)=f (an-1an)-(mn-1-j+1), j∈{1,2,…,mn-1};

f (an-2an-1)=f (an-1an-1,1)-1;

f (an-2an-2, j)=f (an-2an-1)-(mn-2-j+1), j∈{1,2,…,mn-2}

一般地,則有f (akak, j)=f (akak+1)-(mk-j+1), j∈{1,2,…,mk}; f (akak+1)=f (ak+1ak+1, j)-1其中mi=mi-2+mi-1。至此,F(n)圖中所有的邊標號完畢。在圖F(n)中所有邊標號完畢的基礎上對頂點標號,此時讓f滿足

f (an)=0, f (an, j)=2q-2(mn-1)-

f(anan, j)-f (an), j∈{1,2,…,mn};

f (an-1)=f (an,1)+1, f (an-1, j)=2q-2(mn-1-1)-f (an-1an-1, j)-f (an), j∈{1,2,…,mn-1};

f (an-2)=f (an-1, j)+1, f (an-2, j)=2q-2(mn-2-1)-f (an-2an-2, j)-f (an-2), j∈{1,2,…,mn-2};

一般地,當f (ak)=f (ak+1, j)+1時, f (ak,j)=2q-2(mk-1)-f (akak, j)-f (ak),

j∈{1,2,…,mk};其中mi=mi-2+mi-1。

由以上定義的F(n)的標號f可得f (u)+f(uv)+f (v)=2q-2(mj-1), j∈{1, 2, …,n}; 對任意的uv∈E(F(n)), 記λ=2q-2(mj--1)則λ為一常數(shù)。

由邊魔幻全標號的定義知,f 為1-斐波納契毛毛蟲樹的邊魔幻全標號。所以,任何一棵1-斐波納契毛毛蟲樹都有一個邊魔幻全標號。

圖3例舉一個邊魔幻全標號斐波納契毛毛蟲樹的例子。

圖3 1-斐波納契毛毛蟲樹F(7) 的邊魔幻全標號Fig.3 The edge-magic total labelling of 1-Fibonacci′s caterpillar tree F(7)

定理4 1-斐波納契毛毛蟲超級同構(gòu)圖都是二分奇優(yōu)美的。

證 明 設 F(n)為1-斐波納契毛毛蟲同構(gòu)圖,定義F(n)的一個標號f 如下,

先對F(n)的邊標號:

f (an-1an)=2q-1; f (an-1an-1, j)=

2q-1-2(mn-1-j+1), j∈{1,2,…,mn-1};

f (an-2an-1)=f (an-1an-1,1)-2;

f (an-2an-2, j)=f (an-2an-1)-2(mn-2-j+1), j∈{1,2,…,mn-2};

f (an-3an-2)=f (an-2an-2,1)-2;

f (an-3an-3, j)=f (an-3an-2)-2(mn-3-j+1),j∈{1,2,…,mn-3};

一般地,f (ak-1ak)=f (akak,1)-2, f(ak-1ak-1,j)=f (ak-1ak)-2(mk-1-j+1), j∈{1,2,…,mk-1}; 其中mi=mi-2+mi-1。

由以上定義的邊標號f可知,f (an-1an)=2q-1=2|E(F(n))-1|為F(n) 中邊標號的最大值且為奇數(shù)。又因為F(n)為(p, q)-圖,含q條邊,且集合{1, 3, 5,…,2q-1}中元素個數(shù)為2q-1,則定義的F(n)的邊標號f滿足f (E(F(n)))={1, 3, 5,…, 2|E(F(n))-1|}。 至此,F(n)的所有邊標號完畢。下面給 F(n)的頂點標號如下:

f (an)=0, f (an-1)=2q-1; f (an-1,1)=f (an)-2, f (an-2)=f (an-1,1)+2,

f (an-2,1)=f (an-1,1)-2, f (an-3)=f(an-2,1)-2; f (an-3,j)=f (an-2)+2(mn-3-j+1), j∈{1,2,…,mn-3};

f (an-4)=f (an-3,1)+2, f (an-4,j)=

f(an-3)-2(mn-4-j+1), j∈{1,2,…,mn-4};

一般地,當f (ak)=f (ak+1,1)+2 時,f (ak, j)=f (ak+1)-2(mk-j+1), j∈{1,2,…,mk};當f (ak)=f (ak+1,1)-2時,f (ak, j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk};在式 f (ak)=f (ak+1,1)-2 和 f (ak, j)=f (ak+1)-2(mk-j+1), j∈{1,2,…,mk}式下被標號的所有點均為奇數(shù)點,把它們所構(gòu)成的集合記為Y。在式f (ak)=f (ak+1,1)+2和f(ak, j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk} 下被標號的所有點均為偶數(shù)點,把它們所構(gòu)成的集合記為X。

這樣,F(n)的頂點集的二部劃分為(X, Y),其中X表示標號數(shù)為偶數(shù)的點,Y 表示標號數(shù)為奇數(shù)的點。每次所標的偶數(shù)點值是從0開始依次遞增的,每次所標的奇數(shù)點值是從2q-1開始依次遞減的,又因為F(n)為(p, q)-圖且邊標號的最大值為2q-1,綜上可得 f (X)

圖4 例舉一個二分奇優(yōu)美標號斐波納契毛毛蟲超級同構(gòu)圖的例子。

圖4 1-斐波納契毛毛蟲超級同構(gòu)圖F(a5a0)的二分奇優(yōu)美標號Fig.4 The bipartite odd-graceful labelling of 1-Fibonacci′s caterpillar super isomorphic graph F(a5a0)

2 結(jié)論與問題

本文利用邊標號給出了所有的1-斐波納契毛毛蟲樹都為二分奇優(yōu)美樹的證明。并用此方法證明了每一個1-斐波納契毛毛蟲樹的優(yōu)美性和邊魔幻全標號性及它的超級同構(gòu)圖的二分奇優(yōu)美性。文中采取的方法大大減少了標號的難度，這種逆向思維也為我們今后看待和考慮事物提供更多的思路。

問題 根據(jù)本文從邊先標號的特色是否可推廣大至更高層數(shù)的斐波納契毛毛蟲樹也是二分奇優(yōu)美的?

[1] ROSA A.On certain valuations of the vertices of a graph[C]∥Theory of Graphs, International Symposium, Rome.New York:Gordon and Breach, 1967:349-355.

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

[3] GALLIAN J A, A dynamic survey of graph labelling[J].The Electronic Journal of Combinatorics, 2009, 12:42-43.

[4] HE Dan, LIN Wensong. L12-edge-labelling for neekloce[J].Journal of Sontheast University English Edition, 2014,30(4):550-554.

[5] GNANAJOTHI R B. Topics in graph theory[D].Thesis:Madurai Kamaraj University, 1991.

[6] BONDY J A, MURTY U S R.Graph Theory[M].London:Springer, 2008.

[7] BAZZARO F,MONTASSIER M, RASPAUD A.1d,D-total labeling of planar graphs with large girth and high maximum degree[J].Discrete Mathematics,2007,307(16):2141-2151.

[8] BONDY J A, MURTY U S R.Graph Theory with Applications[M].London:The Macmillan Press, 1976.

[9] 劉家保,陳中華.一類二部圖的奇優(yōu)美性[J]. 佛山科學技術(shù)學院學報 (自然科學版), 2013, 31(1):016-019.

[10] 劉家保,陳中華.一類新圖的奇優(yōu)美性的研究[J].汕頭大學學報 (自然科學版), 2012, 27(4):001-003.[11] 姚兵,張家娟,郭璟霞. 復合毛毛蟲樹的優(yōu)美性及奇優(yōu)美性[J]. 蘭州理工大學學報, 2012, 38(4):147-151.

[12] 周向前,姚兵,陳祥恩. 探討奇優(yōu)美樹猜想[J]. 山東大學學報(理學版), 2012, 47(12):31-36.

[13] YAO Bing, CHENG Hui, YAO Bing, et al. A Note on Strongly Graceful Trees[J]. Ars Com binatoria, 2009, 92:155-169.

[14] BACA M, BERTAULT F, MAC D J, et al. Vertexantimagic total labellings of graphs [J]. Discuss Match Graph Theory, 2003, 23:67-83.

[15] 王宏宇,姚兵,楊超. 一類特殊對稱圖的邊魔幻性[J]. 四川師范大學學報 (自然科學版), 2013, 36(1):028-033.

(編 輯 亢小玉)

Probing the edge-labellings of Fibonacci′s caterpillars

LIU Xinsheng, WANG Beibei, CHEN Jing, YAO Bing

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

The study is to explore the edge labelling of the Fibonacci′s caterpillar tree. The method is employed which is different from the original concept of graph labelling-starting from the edge labelling for each graph. And taking advantage of the characteristics of edge labelling, the paper mainly discusses the bipartite odd-graceful labelling, edge-graceful labelling and edge-magic total labelling of 1-Fibonacci′s caterpillar tree. Lastly, the paper deliberates the bipartite odd-graceful labelling of the 1-Fibonacci′s caterpillar super isomorphic graph. This process saves a lot of complex work, which greatly improves the efficiency of graph labelling.

1-Fibonacci′s caterpillar tree; edge labelling; bipartite odd-graceful labelling; edge-graceful labelling; edge-magic total labelling; super isomorphic graph

2015-03-11

國家自然科學基金資助項目(61163037, 61163054, 61363060)

劉信生,男,河南光山人,教授,從事圖論及其應用研究。

王蓓蓓,女,陜西寶雞人,從事圖論及其應用研究。

O157. 5

A

10.16152/j.cnki.xdxbzr.2016-05-002