一类Hm,n图的优美性和强协调性

严谦泰

(安阳师范学院 数学与统计学院，河南 安阳 455000)

0 引言

最近十几年来，优美图由于其有趣性及较好的应用价值和研究前景，其研究十分活跃。国内外取得不少优美图的研究成果[1]，它们也被用于许多领域[2]。它的研究始于1963年Ringel G.的一个猜想[3]和1966年Rosa A.的一篇论文[4]。1972年，Golomb S.W.明确给出了优美图的定义[5]。之后，Gnanajoethi又提出了每棵树都是奇优美的[6]，开始了奇优美图的研究。之后，又提出优美标号的概念[2]。但由于缺少系统和有力的工具，因此至今只能对一些特殊图类研究其优美性.1982年，D·Fank Hsu引入图的强协调标号，现已有许多这方面的结果.之后，作者提出了奇强协调图和强协调图的概念，拓宽强协调标号问题的研究。

定义1[2]对于简单图G=〈V,E〉，如果存在一个映射f:V(G)→{0,1,2,…,|E|}，满足1)对任意的u,v∈V,若u≠v,则f(u)≠f(v)；2)max{f(v)|v∈V}=|E|；3)对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv；4){g(e)|e∈E}={1,2,…,|E|},则称G为优美图，称f为G的优美标号。

定义2[2]对于简单图G=〈V,E〉，如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}，满足1)对任意的u,v∈V，若u≠v,则f(u)≠f(v)；2)max{f(v)|v∈V}=2|E|-1；3)对任意的e1，e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv；4){g(e)|e∈E}={1,3,5,…,2|E|-1}，则称G为奇优美图，称f为G的奇优美标号。

定义3[3]对于简单图G=〈V,E〉，如果存在一个映射f:V(G)→{0,1,2,…,|E|+k-1}，满足1)对任意的u,v∈V，若u≠v,则f(u)≠f(v)；2)max{f(v)|v∈V}=|E|；3)对任意的e1，e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv；4){g(e)|e∈E}={k,k+1,…,k+|E|-1}，则称G为k-优美图，称f为G的k-优美标号。

定义4[5]设G=〈V,E〉是一个无向简单图，如果存在一个映射f:V(G)→{0,1,2,…,|E|}，满足：1)f是单射；2)∀uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1，2，…，|E|}，则称G是强协调图，f为G的强协调标号。

定义5[7]设G=〈V,E〉是一个无向简单图，如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}，满足：(1)f是单射；2)∀uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1，3，5，…，2|E|-1}，则称G是奇强协调图，f为G的奇强协调标号或奇强协调值。显然f导出了一个E(G)与{1，3，5，…，2|E|-1} 的一一对应。

定义6[7]设G=〈V,E〉是一个无向简单图，如果存在一个映射f:V(G)→{0,1,2,…,|E|+k-1}，满足：(1)f是单射；2)∀uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={k，k+1，…，k+|E|-1}则称G是k-强协调图，f为G的k-强协调标号。

本文构造并研究了一类图的优美性和强协调性。未加说明的术语和记号见文献[2]。

1 主要结论及证明

n(n≥2)条具有两个公共端点u1和u2且长度都为2的路构成的图记为An，设V(An)={u1,v1,v2,…,vn,u2}。顺序把前一个An的顶点vn-1与后一个An的顶点u1连一条边，u2与后一个An中顶点vn连一条边所得图记为Hm,n。记Hm,n中m个An为An1,An2,…,Anm给Hm,n的顶点重新标识后的顶点集为：

V(Hm,n)={u11,u21,…,um1，u12,u22,…,um2,v0,v1,v2,…,vm(n-1)}

其中，ui1,ui2(i=1,2,…,m)是Ani中n条路的公共端点，v0,v1,…,vn-1是An1中与u11,u12相邻顶点，vn,vn+1,…,v2n-1是An2中与u21,u22相邻顶点，以此类推。vn-1与u21相邻，u12与vn相邻；v2n-1与u31相邻，u22与v2n相邻，以此类推。显然有|V(Hm,n)|=m(n+2)，|E(Hm,n)|=2mn+2(m-1)。

定理1Hm,n是优美图。

证明给出Hm,n各顶点标号如下：

f(vi)=i,i=0,1,2,…,n-1；

f(vi)=f(vi-n)+n+1,i=n,n+1,n+2,…,mn-1；

f(ui1)=|E(Hm,n)|-(n+1)(i-1),i=1,2,…,m；

f(ui2)=f(ui1)-n,i=1,2,…,m

易验证f是Hm,n的一个优美标号，所以Hm,n是优美图。

定理2Hm,n是奇优美图。

证明给出Hm,n各顶点标号f如下：

f(vi)=2i,i=0,1,2,…,n-1；

f(vi)=f(vi-n)+2(n+1),i=n,n+1,n+2,…,mn-1；

f(ui1)=2|E(Hm,n)|-2(n+1)(i-1),i=1,2,…,m；

f(ui2)=f(ui1)-2n,i=1,2,…,m

易验证f是Hm,n的一个奇优美标号，所以Hm,n是奇优美图。

定理3Hm,n是k-优美图。

证明给出Hm,n各顶点标号f如下：

f(vi)=k+|E(Hm,n)|-1-i,i=0,1,2,…,n-1；

除了关税，自由贸易港更有赖于没有或尽可能少的非关税贸易壁垒，要求对商品、服务进出口，以及贸易项下资金流入流出，不实行或尽可能少实行管制政策。以香港为例，《中英联合声明》附件规定：香港保持自由港地位，并继续实行自由贸易政策，由此可以看出自由港和自由贸易其实是两个不同的概念。香港《基本法》第115条规定：香港实行自由贸易政策，保障货物、无形财产和资本的流动自由。国务院《关于全面深化中国(上海)自由贸易试验区改革方案》要求上海自由贸易港“对标国际最高水平，实施更高标准的‘一线放开、二线安全高效管住’贸易监管制度。”

f(vi)=f(vi-n)-(n+1),i=n,n+1,n+2,…,mn-1；

f(ui1)=(n+1)(i-1),i=1,2,…,m；

f(ui2)=f(ui1)+n,i=1,2,…,m

易验证f是Hm,n的一个k-优美标号，所以Hm,n是k-优美图。

定理4Hm,n是奇强协调图。

证明给出Hm,n各顶点标号f如下：

f(vi)=2i+1,i=0,1,2,…,n-1；

f(vi)=f(vi-n)+2(n+1),i=n,n+1,n+2,…,mn-1；

f(ui2)=f(ui1)+2n,i=1,2,…,m

易验证f是Hm,n的一个奇强协调标号，所以Hm,n是奇强协调图。

定理5Hm,n是k-强协调图。

证明给出Hm,n各顶点标号f如下：

f(vi)=k+i,i=0,1,2,…,n-1；

f(vi)=f(vi-n)+n+1,i=n,n+1,n+2,…,mn-1；

f(ui1)=(n+1)(i-1),i=1,2,…,m；

f(ui2)=f(vi1)+n,i=1,2,…,m

易验证f是Hm,n的一个k-强协调标号，所以Hm,n是强协调图。