刘家保,吕宁宁,余国锋

(安徽新华学院公共基础部,安徽合肥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可得：

很……