唐保祥，任 韩

(1.天水师范学院数学与统计学院，甘肃 天水 741001； 2.华东师范大学数学系，上海 200062)

·研究简报·

两类图及其冠的优美标号

唐保祥1，任 韩2

(1.天水师范学院数学与统计学院，甘肃 天水 741001； 2.华东师范大学数学系，上海 200062)

用构造法对两类图和两类图的冠的优美性进行了研究，得到了如下结论：对任意正整数m和n，设Em和Pn分别是m个顶点的空图和有n+1个顶点的路，那么完全3部图K1，m，n，I(K1，m，2)，联图Em∨Pn和I(E2∨P2n)都是优美图.

路；联图；空图；冠；优美图

1 预备知识

优美图的研究理论已有广泛应用，但是目前没有系统理论对一般图的优美性进行研究.[1-12]马克杰教授在文献[1]中提出猜想：所有优美图的冠都是优美图.这一猜想至今没有被证明或否定.若这个猜想正确，那么优美图的冠都是优美图，于是就有很多图类被证明是优美图，这将是一个很有意义的结论.对任何正整数m和n，本文用构造的方法给出了图K1，m，n，I(K1，m，2)，联图Em∨Pn和I(E2∨P2n)的优美标号，从而证明了这四类图都是优美图.

定义1[1]图G的每个顶点上都粘接1条悬挂边得到的图，称为图G的冠，记作I(G).

定义2[1]设图G=(V，E).若存在单射θ：V(G)→{0，1，2，…，|E(G)|}，使得∀e=uv∈E(G)，由θ′(e)=|θ(u)-θ(v)|导出双射θ′：E(G)→{1，2，…，|E(G)|}，则称图G是优美图，θ称为图G的一个优美标号，θ′称为由θ导出的边标号.

2 主要结果及其证明

定理1 ∀m，n∈Z+，完全3部图K1，m，n是优美图.

证明显然|E(K1，m，n)|=mn+m+n，|V(K1，m，n)|=m+n+1.设V(K1，m，n)={v1，v2，…，vm，w，u1，u2，…，un}.定义图K1，m，n顶点的标号θ如下：

θ(vi)=mn+m+n+1-i，i=1，2，…，m；θ(w)=mn+n；θ(ui)=(m+1)(i-1)，i=1，2，…，n.

图1 图K1,5,4的优美标号

例如，图K1，5，4的优美标号如图1所示.

令S1={θ(vi)|i=1，2，…，m}∪{mn+n}，S2={θ(ui)|i=1，2，…，n}，则S1∪S2={0，m+1，2(m+1)，…，(n-1)(m+1)，mn+n，mn+n+1，…，mn+n+m}，S1∩S2=∅.因此映射θ：V(K1，m，n)→{0，1，2，…，mn+m+n}是单射.

显然θ(v1)-θ(u1)，θ(v2)-θ(u1)，…，θ(vm)-θ(u1)，θ(w)-θ(u1)，θ(v1)-θ(u2)，θ(v2)-θ(u2)，…，θ(vm)-θ(u2)，θ(w)-θ(u2)，…，θ(v1)-θ(un)，θ(v2)-θ(un)，…，θ(vm)-θ(un)，θ(w)-θ(un)，θ(v1)-θ(w)，θ(v2)-θ(w)，…，θ(vm)-θ(w)是首项为mn+m+n，尾项是1，公差是-1的等差数列，所以θ′：E(K1，m，n)→{1，2，…，mn+m+n}是双射，故θ是图K1，m，n的一个优美标号，图K1，m，n是优美图.

定理2 ∀m∈Z+，图K1，m，2的冠I(K1，m，2)是优美……