一致仙人掌树的Felicitous性质

杨思华　姚兵

摘 要 利用较小的具有集有序Felicitous性质的树构造较大规模的具有Felicitous性质的树，并揭示了集有序Felicitous树与集有序优美树的等价关系.

关键词 一致仙人掌树；Felicitous标号；集有序Felicitous标号；集有序优美标号

中图分类号 O1575文献标识码 A文章编号 10002537（2014）03008704

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

1 预备知识

本文涉及的图均为有限、无向简单图.文中没有定义的术语和符号均来自文献[13]. 为叙述简便，我们把一个有p个顶点q条边的连通图记为（p，q）图.记号[m，n]表示非负整数集合{m，m+1，m+2，…，n}，其中m和n均为整数，且满足0≤m

定义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}

定义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）

摘 要 利用较小的具有集有序Felicitous性质的树构造较大规模的具有Felicitous性质的树，并揭示了集有序Felicitous树与集有序优美树的等价关系.