关于一类树的优美标号

刘家保,吕宁宁,余国锋

(安徽新华学院公共基础部,安徽合肥230088)

0 引 言

优美图是图论中极其有趣的内容,是一类特殊的简单无向图.优美图的研究始于1963年 G·Ringel提出的一个猜想和1966年A·Rosa的一篇论文[1].1972年,S.W.Golomb明确给出了优美图的概念.优美图的优美标号可应用于编码理论、通信网络、射电天文学、导弹控制码设计等方面,一直以来深受人们的重视,迄今,已有许多这方面的成果[1-6].但由于对优美图的研究缺乏一个系统和有力的工具,所以目前只能对一些特殊的图类探索其优美性.

1 预备知识

定义1 图 G的一个顶点标号L,是指从V(G)到 {0,1,2,…,|V|},且u,v不同时,有L(u)≠L(V).

定义2 简单图 G的一个优美标号,是指 G的一个顶点标号L,它满足：当 G的边e=uv时,由L′(e)=|L(u)-L(V)|决定的边标号L′,会分配给各边以不同的标号,这时L′为 E(G)到{1,2,…,|E|}的双射.若简单图G有优美标号L,则称 G为优美图.

图1 图 的图示

为了叙述方便,本文规定,文中所讨论的图均为简单无向图,其他未加说明的定义和符号均请参考文献[7].

2 结论及其证明

情况一：当 h≡1(mod2),(不妨设 h=2s-1).给出图的各顶点的标点递推算法A如下：

证明 设 S1={L(ai)|1≤i≤m},S2={L(bi)|1≤j≤n},S3={L(cj)|1≤j≤h}=S31∪S32,其中 S31={L(cj)|1≤j≤h},j为奇数},S32={L(cj)|1≤j≤h,j为偶数},则有算法 A可得:

很清楚每个顶点的标号各不相同,并且满足Max{L(V)}=m+n+h=|E|,因此L是从顶点集合V()到 {0,1,…,m+n+h}的一一映射函数,从而顶点集与集合 {0,1,2,…,m+n+h}构成单射.

从而 L′(chb1)＜L′(chb2)＜ …＜L′(a2c0)＜L′(a1c0)

边标号的集合:

即1＜2＜…＜2n-1＜m+n+h,从而所有不同的边有不同的标号,综上所述图的边集与集合 {1,2,…,m+n+h}构成一一对应.

情况二：当 n≡0(mod2),(不妨设 h=2s)给出图的各顶点的标点递推算法B如下：

算法B：L (ai) =m+n+h-i+1,(i=1,2,…,m)

证明 设S1={L(ai)|1≤i≤m},S2={L(bj)|1≤j≤n},S3={L(cj)|1≤j≤h}=S31∪S32,其中 S31={L(cj)|1≤j≤h,j为奇数},S32={L(cj)|1≤j≤h,j为偶数},则有算法B可得：

很清楚每个顶点的标号各不相同,并且满足Max{L(V)}=m+n+h=|E|,因此L是从顶点集合V()到 {0,1,…,m+n+h}的一一映射函数,从而顶点集与集合 {0,1,2,…,m+n+h}构成单射.

由算法B知

边标号的集合:

即1＜2＜…＜2n-1＜m+n+h,从而所有不同的边有不同的标号,

定理1的证明,由引理1～4及优美图的定义可知,对∀m,n,h∈N,图是优美图.

图2 双星图的优美标号

图3 一条路的优美符号

3 例 子

图4 图的优美符号

图5 图的优美符号

4 结束语

本文用了比较简单的方法研究了一类优美树的优美性,证明了一类树是优美的.优美树的研究是一个非常有趣的课题,得到了国际上许多数学家的高度关注,希望更多的研究者加入进来.另外,除了简单连通无向图,非连通图,并图以及有向图是否具有优美标号也是值得思考的问题.

[1] Rosa A.On Certain Valuations of the Vertices of a Graph,Theory of Graphs[M].Rome：Proc Internat,1966：20-83

[2] 刘家保.一类单圈图的优美性和平衡性 [J].合肥学院学报,2008,18(02)：18-22

[3] 刘家保.轮形图和扇形图的优美性 [J].安徽大学学报,2009,33(04)：11-13

[4] 林育青.Cn与1Cn的优美标号 [J].安徽大学学报,2007,17(02)：12-16

[5] 邓怀敏,图的优美标号 [J].新疆大学学报,2000,17(02)：12-16

[6] 林育青.一类图的优美性 [J].云南师范大学学报,2004,24(04)：15-19

[7] Abondy J,Rmurty US.Graph Theory with Appllications[M].London：Macmillan Press,1976：10-70