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

(西北师范大学 数学与统计学院,甘肃 兰州 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的顶点标号,使其满足特定的条件,这是本文的创新之处。……