刘家保， 王 林， 陆一南

（安徽新华学院公共课教学部，安徽合肥 230088）

0 引 言

关于图的优美性，文献［1］提出“所有的树都是优美的”著名优美树猜想，奇优美标号是一类特殊的优美标号，具有奇优美标号的图类是奇优美图。文献［2］给出了优美图的定义。到目前为止，国内外已取得很多关于优美图的研究成果［1－9］。本文研究一类具有公共边的双圈图奇优美标号。

1 基本概念

定义1 对于一个简单图G＝（V，E）有a个顶点和b条边，存在函数L：V（G）→｛0，1，2，…，2b－1｝是单射的，诱导出函数L′：E（G）→｛1，3，…，2b－1｝，且L′（e＝uv）＝｜L（u）－L（v）｜是双射的，称图G具有奇优美标号，且称图G为奇优美图［1］。

定义2 2个圈图Cn共享一条公共边的图类，记为双圈图D（n），设Cn∩Cn＝e＝uv，u，v∈V（D（n）），e＝uv∈E（D（n）），双圈图D（n）满足以下条件：

（2）顶点集V（D（n））＝｛vi｜1≤i≤n｝，顶点数｜V（D（n））｜＝2n－2。

（3）边集E（D（n））＝｛vivi＋1｜1≤i≤2n－3｝∪｛v2n－2v1｝∪｛v（n＋2）／2v3n／2｝，边数｜E（D（n））｜＝2n－1。

2 主要结果

定理1 对∀n∈N＊，n≡0（mod 4）或者n≡2（mod 4），双圈图D（n）是奇优美图。

证明 双圈图D（n）顶点数为｜V（D（n））｜＝2n－2，边数为｜E（D（n））｜＝2n－1，2个单圈图公共的一条边为e＝v（n＋2）／2v3n／2。定义函数L： V（D（n））→｛0，1，2，…，2｜E（D（n））｜－1｝＝｛0，1，2，…，4n－3｝，边标号定义为L′（piqj）＝｜L（pi）－L（qj）｜，其中pq∈E（D（n）），给出图D（n）各顶点的标号算法。

2.1 情形1（n≡0（mod 4））

（1）当1≤i≤n＋1时，有

（2）当n＋2≤i≤3n／2时，有

首先证明L是从顶点集V（D（n））到｛0，1，2，…，4n－3｝的单射函数。

令A＝｛L（vi）｜1≤i≤2n－2｝，则

因此，A＝A1∪A2∪A3∪A4∪A5∪A6是所有顶点标号的集合，且有：

由上可知，A⊆｛0，1，2，…，4n－3｝，所有顶点的标号是各不相同的，所以L是一个从V（D（n））到｛0，1，2，…，4n－3｝的单射函数。

其次，证明L′是从E（D（n））到｛1，3，…，4n－ 3｝的双射函数。

令B＝｛L′（vivi＋1）｜1≤i≤2n－3｝∪｛L′（v（n＋2）／2v3n／2）｝∪｛L′（v2n－2v1）｝，则有：

因为

所以

因此，B＝B1∪B2∪B3是所有边的标号的集合，且有：

由上述可知，每条边的标号是各不相同的，且边的标号的集合为｛1，3，…，4n－3｝，所以L′是一个从E（D（n））到｛1，3，…，4n－3｝的双射函数。

根据奇优美标号的定义，对∀n∈N＊，且图D（n）的n确定，双圈图在n≡0（mod 4）的情形下是奇优美图。

2.2 情形2（n≡2（mod 4））

（1）当1≤i≤n＋1时，有

（2）当n＋2≤i≤3n／2时，有

下面证明L是从顶点集V（D（n））到｛0，1，2，…，4n－3｝的单射函数。

令C＝｛L（vi）｜1≤i≤2n－2｝，则所有顶点标号的集合C⊆｛0，1，2，…，4n－3｝，所有顶点的标号是各不相同的，所以L是一个从V（D（n））到｛0，1，2，…，4n－3｝的单射函数。……