探討斐波納契毛毛蟲樹(shù)的邊標(biāo)號(hào)

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

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

?

·數(shù)理科學(xué)·

探討斐波納契毛毛蟲樹(shù)的邊標(biāo)號(hào)

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

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

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

1-斐波納契毛毛蟲樹(shù);邊標(biāo)號(hào);二分奇優(yōu)美標(biāo)號(hào);邊優(yōu)美標(biāo)號(hào);邊魔幻全標(biāo)號(hào);超級(jí)同構(gòu)圖

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

文中所提到的圖都是簡(jiǎn)單的、無(wú)向的并且是有限的,沒(méi)有定義的術(shù)語(yǔ)和符號(hào)均采自于文獻(xiàn)[8]。為敘述簡(jiǎn)便,我們把一個(gè)有p個(gè)頂點(diǎn)和q條邊的圖叫做 (p,q)-圖。用V(G)和E(G)分別表示樹(shù)G的頂點(diǎn)個(gè)數(shù)和邊數(shù)目。設(shè)一個(gè)(p,q)-圖G有一個(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)}。此外,設(shè)G是具有頂點(diǎn)二部劃分(X,Y)的二分圖,若對(duì)任意的x∈X和y∈Y,標(biāo)號(hào)f滿足f(x)

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

定義1[9-10]樹(shù)G的一個(gè)頂點(diǎn)標(biāo)號(hào)L是指從V (G)到{0,1,…,2|E|-1},且當(dāng)頂點(diǎn)u, v不同時(shí),有L(u)≠L(v)。對(duì)G的邊e=uv,定義L′ (e)=|L(u)-L(v)|為邊uv的邊標(biāo)號(hào),當(dāng) E(G)的主軸標(biāo)號(hào)為{1,3,…,2|E|-1},則說(shuō)L為簡(jiǎn)單圖G的奇優(yōu)美標(biāo)號(hào),稱G為奇優(yōu)美圖。

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

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

定義4[14-15]設(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)。

定義5 設(shè)G是(p, q)-圖,若存在一個(gè)映射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)美的。

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

1 主要結(jié)論

定理1 每一棵1-斐波納契毛毛蟲樹(shù)都有一個(gè)邊奇優(yōu)美標(biāo)號(hào),且它是二分奇優(yōu)美標(biāo)號(hào)。

證 明 設(shè) F(n) 為一棵1-斐波納契毛毛蟲樹(shù)。定義F(n)的一個(gè)標(biāo)號(hào)f如下,先給 F(n)的邊標(biāo)號(hào):

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。

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

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};

一般地,當(dāng)f (ak)=f (ak+1,1)-2 時(shí),f (ak, j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk};當(dāng)f (ak)=f (ak+1,1)+2時(shí),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}式下被標(biāo)號(hào)的所有點(diǎn)均為奇數(shù)點(diǎn),把它們所構(gòu)成的集合記為Y。在式f (ak)=f (ak+1,1)+2, f (ak,j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk}下被標(biāo)號(hào)的所有點(diǎn)均為偶數(shù)點(diǎn),把它們所構(gòu)成的集合記為X。

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

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

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

定理2 所有的1-斐波納契毛毛蟲樹(shù)都有邊優(yōu)美標(biāo)號(hào)。

證 明 設(shè)F(n) 為一棵1-斐波納契毛毛蟲樹(shù),定F(n)的一個(gè)標(biāo)號(hào)f如下:先給F(n) 的邊標(biāo)號(hào):

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。

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

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};

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

f (ak, j)=f (ak+1)-(mk-j+1), j∈{1,2,…,mk}; 其中mi=mi-2+mi-1。由以上定義的F(n)的一個(gè)標(biāo)號(hào)f知邊標(biāo)號(hào)的最大值q對(duì)應(yīng)于點(diǎn)標(biāo)號(hào)的最小值 0,從而可得f (V(F(n)))→[0, q]。

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

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

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

定理3 任何一棵1-斐波納契毛毛蟲樹(shù)都有一個(gè)邊標(biāo)號(hào),且它是邊魔幻全標(biāo)號(hào)。

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

證 明 定義1-斐波納契毛毛蟲樹(shù)F(n)的一個(gè)標(biāo)號(hào) f 如下,先對(duì)F(n)的邊標(biāo)號(hào):

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)圖中所有的邊標(biāo)號(hào)完畢。在圖F(n)中所有邊標(biāo)號(hào)完畢的基礎(chǔ)上對(duì)頂點(diǎn)標(biāo)號(hào),此時(shí)讓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};

一般地,當(dāng)f (ak)=f (ak+1, j)+1時(shí), f (ak,j)=2q-2(mk-1)-f (akak, j)-f (ak),

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

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

由邊魔幻全標(biāo)號(hào)的定義知,f 為1-斐波納契毛毛蟲樹(shù)的邊魔幻全標(biāo)號(hào)。所以,任何一棵1-斐波納契毛毛蟲樹(shù)都有一個(gè)邊魔幻全標(biāo)號(hào)。

圖3例舉一個(gè)邊魔幻全標(biāo)號(hào)斐波納契毛毛蟲樹(shù)的例子。

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

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

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

先對(duì)F(n)的邊標(biāo)號(hào):

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。

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

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};

一般地,當(dāng)f (ak)=f (ak+1,1)+2 時(shí),f (ak, j)=f (ak+1)-2(mk-j+1), j∈{1,2,…,mk};當(dāng)f (ak)=f (ak+1,1)-2時(shí),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}式下被標(biāo)號(hào)的所有點(diǎn)均為奇數(shù)點(diǎn),把它們所構(gòu)成的集合記為Y。在式f (ak)=f (ak+1,1)+2和f(ak, j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk} 下被標(biāo)號(hào)的所有點(diǎn)均為偶數(shù)點(diǎn),把它們所構(gòu)成的集合記為X。

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

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

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

2 結(jié)論與問(wèn)題

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

問(wèn)題 根據(jù)本文從邊先標(biāo)號(hào)的特色是否可推廣大至更高層數(shù)的斐波納契毛毛蟲樹(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]. 佛山科學(xué)技術(shù)學(xué)院學(xué)報(bào) (自然科學(xué)版), 2013, 31(1):016-019.

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

[12] 周向前,姚兵,陳祥恩. 探討奇優(yōu)美樹(shù)猜想[J]. 山東大學(xué)學(xué)報(bào)(理學(xué)版), 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] 王宏宇,姚兵,楊超. 一類特殊對(duì)稱圖的邊魔幻性[J]. 四川師范大學(xué)學(xué)報(bào) (自然科學(xué)版), 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

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

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

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

O157. 5

A

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