探讨斐波纳契毛毛虫树的边标号

刘信生，王蓓蓓，陈 璟,姚 兵

(西北师范大学 数学与统计学院,甘肃 兰州 730070)



·数理科学·

探讨斐波纳契毛毛虫树的边标号

刘信生，王蓓蓓，陈 璟,姚 兵

(西北师范大学 数学与统计学院,甘肃 兰州 730070)

为了探讨斐波纳契毛毛虫树的边标号,采用不同于原定义的图标号的方法-先从边对每个图进行标号。利用先从边标号的特点,主要讨论了1-斐波纳契毛毛虫树的边二分奇优美标号,边优美标号及边魔幻全标号。最后讨论了1-斐波纳契毛毛虫超级同构图的二分奇优美标号。这样的方法省去了大量繁复工作,大大提高了图标号的效率。

1-斐波纳契毛毛虫树;边标号;二分奇优美标号;边优美标号;边魔幻全标号;超级同构图

1966年,Rosa[1]提出了一个猜想:每一棵树都是优美树。关于这个猜想已经有了很多的结果,但是一直没有彻底的解决,进而使得优美树猜想至今仍是一个吸引人的困难问题。对于数学猜想的进攻,导致图的着色和标号迅速发展成为当今图论学科中十分活跃的分支,它们在编码理论、通讯网络、物流等方面均有着重要的应用[2-7]。

文中所提到的图都是简单的、无向的并且是有限的,没有定义的术语和符号均采自于文献[8]。为叙述简便,我们把一个有p个顶点和q条边的图叫做 (p,q)-图。用V(G)和E(G)分别表示树G的顶点个数和边数目。设一个(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的顶点标号,使其满足特定的条件,这是本文的创新之处。我们发现,一旦图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的奇优美标号,称G为奇优美图。

定义2[11-12]对于给定的(p, q)-图G,如果存在一个映射 f: V→[0,2q-1],使得 f (V(G))=p和 f (E(G))={1,3,5,…,2q-1},则称G是奇优美图,称f是G的一个奇优美标号。此外,若G是具有顶点二部划分(X, Y)的二分图,且f满足 f (X)

定义3[13]对于给定的(p, q)-图G,如果存在一个映射f: V(G)→[0, q],使得 f(E(G))=[1, q],则称f是G的一个优美标号,也称G是优美图。

定义4[14-15]设G是(p, q)-图,若存在常数λ和双射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的边优美映射,G为边优美的。

设 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-斐波纳契毛毛虫树对应位置的对应顶点之间加一条关联边所构成的图称为1-斐波纳契超级同构图。

1 主要结论

定理1 每一棵1-斐波纳契毛毛虫树都有一个边奇优美标号,且它是二分奇优美标号。

证 明 设 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)中边标号的最大值且为奇数。又因为F(n)为(p, q)-图,含q条边,且集合{1,3,5,…,2q-1}中元素个数为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}式下被标号的所有点均为奇数点,把它们所构成的集合记为Y。在式f (ak)=f (ak+1,1)+2, f (ak,j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk}下被标号的所有点均为偶数点,把它们所构成的集合记为X。

这样,F(n)的顶点集的二部划分为(X, Y),其中X表示标号数为偶数的点,Y表示标号数为奇数的点。每次所标的偶数点值是从0 开始依次递增的,每次所标的奇数点值是从2q-1开始依次递减的,又因为F(n)为(p, q)-图且边标号的最大值为2q-1,所以综上可得 f (X)

图1例举一个二分奇优美斐波纳契毛毛虫树例子。

图1 1-斐波纳契毛毛虫树F(6) 的二分奇优美标号Fig.1 The bipartite odd-graceful labelling of 1-Fibonacci′s caterpillar tree F(6)

定理2 所有的1-斐波纳契毛毛虫树都有边优美标号。

证 明 设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}中元素个数为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]。

由优美标号的定义,可得f为1-斐波纳契毛毛虫树的优美标号。所以1-斐波纳契毛毛虫树都是优美树。

图2例举一个优美斐波纳契毛毛虫树的例子。

图2 1-斐波纳契毛毛虫树F(7)的优美标号Fig.2 The graceful labelling of 1-Fibonacci′s caterpillar tree F(7)

定理3 任何一棵1-斐波纳契毛毛虫树都有一个边标号,且它是边魔幻全标号。

在中国发展西洋歌剧，就必须面对许多的现实问题，由于中国的历史文化的源远流长，深入人心必然会影响西方歌剧在中国的传播。从这个方面来说，延安秧歌剧发展对我国认识西方歌剧有着很好的过渡意义，也对我国创作第一部民族歌剧《白毛女》有着先导作用。

证 明 定义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)则λ为一常数。

由边魔幻全标号的定义知,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-斐波纳契毛毛虫超级同构图都是二分奇优美的。

证 明 设 F(n)为1-斐波纳契毛毛虫同构图,定义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) 中边标号的最大值且为奇数。又因为F(n)为(p, q)-图,含q条边,且集合{1, 3, 5,…,2q-1}中元素个数为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}式下被标号的所有点均为奇数点,把它们所构成的集合记为Y。在式f (ak)=f (ak+1,1)+2和f(ak, j)=f (ak+1)+2(mk-j+1), j∈{1,2,…,mk} 下被标号的所有点均为偶数点,把它们所构成的集合记为X。

这样,F(n)的顶点集的二部划分为(X, Y),其中X表示标号数为偶数的点,Y 表示标号数为奇数的点。每次所标的偶数点值是从0开始依次递增的,每次所标的奇数点值是从2q-1开始依次递减的,又因为F(n)为(p, q)-图且边标号的最大值为2q-1,综上可得 f (X)

图4 例举一个二分奇优美标号斐波纳契毛毛虫超级同构图的例子。

图4 1-斐波纳契毛毛虫超级同构图F(a5a0)的二分奇优美标号Fig.4 The bipartite odd-graceful labelling of 1-Fibonacci′s caterpillar super isomorphic graph F(a5a0)

2 结论与问题

本文利用边标号给出了所有的1-斐波纳契毛毛虫树都为二分奇优美树的证明。并用此方法证明了每一个1-斐波纳契毛毛虫树的优美性和边魔幻全标号性及它的超级同构图的二分奇优美性。文中采取的方法大大减少了标号的难度，这种逆向思维也为我们今后看待和考虑事物提供更多的思路。

问题 根据本文从边先标号的特色是否可推广大至更高层数的斐波纳契毛毛虫树也是二分奇优美的?

[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] 刘家保,陈中华.一类二部图的奇优美性[J]. 佛山科学技术学院学报 (自然科学版), 2013, 31(1):016-019.

[10] 刘家保,陈中华.一类新图的奇优美性的研究[J].汕头大学学报 (自然科学版), 2012, 27(4):001-003.[11] 姚兵,张家娟,郭璟霞. 复合毛毛虫树的优美性及奇优美性[J]. 兰州理工大学学报, 2012, 38(4):147-151.

[12] 周向前,姚兵,陈祥恩. 探讨奇优美树猜想[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