图的奇优美性与奇强协调性

林育青，钟发胜，曹 蓉，童细心

（汕头职业技术学院自然科学系，广东 汕头 515041）

0 引言

优美图的提出始于1963年G.Ringel[1]的一个猜想和1967 A.Rosa[2]的一篇论文.1972年，S.W.Golomb[3]明确给出了优美图的定义.1982年，Fank Hsu D[4]引入图的强协调标号；1994年，Gnanajoethi提出另一个猜想：“每棵树都是奇优美的”[5-6]，又推动了对图的奇优美性和奇强协调性的研究，也取得了一些成果[7-18].但由于缺乏一个系统和有力的工具，迄今，只能对一些特殊图探索其奇优美性和奇强协调性.本文给出了图的定义，讨论了图的奇优美性与奇强协调性并给出了标号算法.

定义 1[5]对于简单图 G＝（V，E），如果存在一个映射满足：1）f是单射；2）有：

则称图G是奇优美图，f称为G的奇优美标号.

定义 2[4]对于简单图 G＝（V，E），如果存在一个映射满足：1）f是单射；2），令f（uv）＝f（u）＋f（v）有：

则称图G是奇强协调的，f称为G的奇强协调标号.

定义3[7]在含有n个顶点的路Pn上，当且仅当两点的距离为m（m≥2）时增加一条边，这样所得到的图称为.

定义4在含有n个顶点的路Pn上，当且仅当两点的距离为m（m≥2）时增加一条长度为2的边，这样所得到的图称为的细分图，记为.

图 1 图

本文所讨论的图均为无向简单图，其它未加说明的定义和符号均来自文献[19].

1 主要结果及证明

下面分两种情形证明.

（1）v2i－1＝vi，i，i＝1，2，…，k；

（2）v2i＝vi＋1，i，i＝1，2，…，k；

（3）v2i－1，2i＋1＝vi，i＋1，i＝1，2，…，k－1；

（4）v2i，2i＋2＝vi＋1，i－1，i＝1，2，…，k－1.

图 2 图P（2k，2）的顶点标记

下面给出P（2k，2）的顶点标号算法A：

算法A（1）f（vi，i＋1）＝（12k－7）－6i，i＝1，2，…，k－1；

（2）f（vi，i）＝6i－6，i＝1，2，…，k

（3）f（vi＋1，i）＝（12k－5）－6i，i＝1，2，…，k

（4）f（vi＋2，i）＝6i－2，i＝1，2，…，k－1

下面验证算法A是图P（2k，2）的一个奇优美标号算法，从而也是图的一个奇优美标号算法.

图 3 图 P（2k＋1，2）的顶点标记

综上，由引理2.3、2.4及定义2，当n＝2k＋1时，图是奇强协调图，即情形4成立.

2 实例

图4 图的奇优美标号

图 5 图的奇优美标号

图6 图的奇强协调标号

图 7 图的奇强协调标号