一致仙人掌树的Felicitous性质

杨思华，姚 兵，张婉佳

(西北师范大学数学与统计学院，中国兰州 730070)

1996年，Rosa［1］提出了一个猜想:每一棵树都是优美树.后来，Bermond［2］又提出了猜想:所有龙虾树都是优美树.关于这两个猜想已经有了很多结果，但是一直没有彻底地解决.Sin-Min Lee［3］等人于1991年提出了猜想:每一棵树都是Felicitous树.该猜想与优美树猜想具有同等的理论价值，而且具有相同的难度，都是NP-hard问题［4-12］.对于数学猜想的进攻，导致图的标号迅速发展成为当今图论学科中十分活跃的分支，它在编码理论、通讯网络、物流等方面均有着重要应用.

1 预备知识

本文涉及的图均为有限、无向简单图.文中没有定义的术语和符号均来自文献［13］.为叙述简便，我们把一个有 p个顶点q条边的连通图记为(p，q)-图.记号［m，n］表示非负整数集合{m，m+1，m+2，…，n}，其中m 和 n均为整数，且满足0≤m ＜n;［k，l］e表示偶数集{k，k+2，k+4，…，l}，其中 k和 l为偶数，且满足0≤k ＜l;［s，t］o表示奇数集{s，s+2，s+4，…，t}，其中 s和 t是满足1≤s＜t的奇数.

定义1 设G是(p，q)-图，若存在一个单射f:V(G)→［0，q］，使得边标号集合{f(uv)|uv∈E(G)}=［0，q－1］，其中边标号为f(uv)=f(u)+f(v)(mod q)，那么称G是Felicitous图，并称f是G的一个Felicitous标号.

对于定义1中的图G和Felicitous标号f，以下简记顶点标号集合f(V(G))={f(u)|u∈V(G)}，边标号集合 f(E(G))={f(u)+f(v)|uv∈E(G)}，以及 f(E(G))(mod q)={f(uv)|uv∈E(G)}.

定义2 设(X，Y)是二部图G的顶点集的一个二部划分，如果G有一个Felicitous标号f，使得max{f(x)|x∈X}＜min{f(y)|y∈Y}(以下简记为f(X)＜f(Y))，则称G是集有序Felicitous图，也称f是G的一个集有序Felicitous标号.

定义3 设G是(p，q)-图，若存在一个单射f:V(G)→［0，q］，使得边标号集合{f(uv)|uv∈E(G)}=［1，q］，其中边标号为f(uv)=|f(u)－f(v)|，那么称G是优美图，并称f是G的一个优美标号.进一步，设(X，Y)是二部图G的顶点集的一个二部划分，若G有一个优美标号f，使得f(X)＜f(Y)，则称G是集有序优美图，也称f是G的一个集有序优美标号.

定义 4 设 H，T1，T2，…，Tn是树，|H|=n，V(H)={ui|i∈［1，n］}，对每一个 i∈［1，n］，将 H 的顶点 ui和树Ti中的一个顶点重合，得到的图G叫做复合图，特记为G=〈H;T1，T2，…，Tn〉.

定义5 若复合图 G=〈H;T1，T2，…，Tn〉中的 H 是具有偶数个顶点的星 K1，n－1，且 Tk(k∈［1，n］)的顶点集二部划分(Xk，Yk)满足|Xk|=|Yk|=s，则称 G=〈K1，n－1;T1，T2，…，Tn〉为一致仙人掌树.

由定义4可以看出复合图指的同一类图，而定义5中的一致仙人掌树是复合图的一个特例.本文主要是利用较小的具有集有序Felicitous性质的树构造较大的具有Felicitous性质的一致仙人掌树，并给出了集有序Felicitous树与集有序优美树的等价关系.

2 主要结论及其证明

定理1 设 T1，T2，…，Tn是集有序 Felicitous树，每一棵树 Tk(k∈［1，n］)的顶点集二部划分(Xk，Yk)满足|Xk|=|Yk|=s，则一致仙人掌树 G=〈K1，n－1;T1，T2，…，Tn〉(n=2l，l∈N+)具有 Felicitous标号.

证 对k∈［1，n］，设集有序Felicitous树Tk的顶点集二部划分(Xk，Yk)满足|Xk|=|Yk|=s，其中 Xk={uk，i|i∈［1，s］}和 Yk={vk，j|j∈［1，s］}.每一棵树 Tk(k∈［1，n］)具有集有序 Felicitous标号 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］.设星 K1，n－1的顶点集二部划分为(X，Y)，其中 X={x}，Y={y1，y2，…，yn－1}.

首先将星 K1，n－1中的顶点 x 与 T1的顶点 u1，1重合，再将 K1，n－1的顶点 ya与 Ta+1中的顶点 va+1，s(a∈［1，n－1］o)重合，最后将 K1，n－1的顶点 yb与 Tb+1中顶点 ub+1，1(b∈［1，n －1］e)重合，就得到本定理中的一致仙人掌树G.

下面利用上述n个集有序Felicitous标号fk(k∈［1，n］)给一致仙人掌树G定义一个新标号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与树 Tk(k∈［1，n］)重合的顶点标号记为 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.不难验证 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］.再因为星 K1，n－1的每个顶点与树 Tk(k∈［1，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，即一致仙人掌树 G 有2ns－1 条边.

下面计算 g(E(G))=g(E(T*))(mod 2ns－1)∪g(E(K1，n－1))(mod 2ns－1).首先给出 T*中边 uk，ivk，j的标号

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

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

因为一致仙人掌树 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).当a∈［1，n －1］o时，边xya满足 g(xya)=g(x)+g(ya)=(a+n+1)s－1，从而

当 b∈［1，n －1］e时，边 xyb满足 g(xyb)=g(x)+g(yb)=bs，则有

结合(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］说明 g 是一致仙人掌树 G=〈K1，n－1;T1，T2，…，Tn〉的一个 Felicitous 标号.

注释:图1解释定理1的一个例子.观察一致仙人掌树G=〈K1，9;T1，T2，…，T10〉，我们可看到树T1与T10之间的边(1，158)，(2，157)，(3，156)，(80，79)，(82，77)，(83，76)的每一条边均可替代边(0，159)，从而得到一棵新的具有Felicitous标号的一致仙人掌树.不难发现，对其他树Ts与T1(s∈［2，9］)之间的边存在同样的规律.定理1中的一致仙人掌树G是不唯一的.

图1 解释定理1的一个例子Fig.1 An example for illustrating Theorem 1

定理2 一棵树具有集有序Felicitous标号的充分必要条件是它具有集有序优美标号.

证 设具有 n个顶点的树 T的顶点集二部划分为(X，Y)，这里 X={xi|i∈［1，s］}和Y={yj|j∈［1，t］}，s+t=n.

必要性 设树 T 有一个集有序 Felicitous标号 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的另一个标号 α 如下:α(xi)=h(xi)，i∈［1，s］;α(yj)=h(yt－j+1)，j∈［1，t］;对边 xiyj∈E(T)，有 α(xiyj)=|α(yj)－ α(xi)|=|h(yt－j+1)－h(xi)|.集有序 Felicitous标号 h，满足 h(yj)∈h(xi)，所以 α(xiyj)=h(yt－j+1)－h(xi)=n －(t－j+1)－(i－1)=s+j－i.对 i∈［1，s］和 j∈［1，t］，有 α(xiyj)∈［1，n －1］.由上可知，顶点标号集合 α(V(T))=［0，n－1］，边标号集合 α(E(T))=［1，n－1］.所以，标号 α 是树 T的一个集有序优美标号.

充分性 设树 T 有一个集有序优美标号 f，使得 f(xi)=i－1，i∈［1，s］;f(yj)=s+j－1，j∈［1，t］;对边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 如下:g(xi)=f(xi)，i∈［1，s］;g(yj)=f(yt－j+1)，j∈［1，t］;对边 xiyj∈E(T)，有 g(xiyj)=g(xi)+g(yj)(mod n－1).易知，顶点标号为 g(xi)∈［0，s－1］，g(yj)∈［s，n－1］.由于 g(xi)+g(yj)=f(xi)+f(yt－j+1)=n+i－ j－1，则对 i∈［1，s］和 j∈［1，t］，有 g(xi)+g(yj)∈［n － t，n+s－2］，故边标号 g(xiyj)(mod n－1)∈［0，n－2］.综上，顶点标号集号 g(V(T))=［0，n－1］，边标号集合 g(E(T))(mod n－1)=［0，n－2］.所以，标号g是树T的一个集有序Felicitous标号.

［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］王 鸿，韩培友.两类大龙虾幸福树的构造性证明［J］.郑州大学学报:自然科学版，2000，32(2):4-7.

［7］韩培友，姚 慧.两大类树是幸福树的新证法［J］.河南师范大学学报:自然科学版，2001，29(1):20-26.

［8］何建锋.一类幸福树的构造性证明［J］.楚雄师范学院学报，2002，17(3):36-37.

［9］袁名焱，罗秋红，汤自凯.由星补刻画的一类广义线图［J］.湖南师范大学自然科学学报，2012，35(1):5-8.

［10］王力工，樊稳茹，张 政.多扇图中保Wiener指数的树［J］.湖南师范大学自然科学学报，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.