网格图Z4，n的优美标号和强协调标号

严谦泰

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

1 引言

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

定义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[8]设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的强协调标号.

定义4[10]设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}，满足：(1)f是单射;(2)Vuv∈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}的一个一一对应.

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

2 主要结论及证明

定理1 设C1,C2,…,Cn是n(n≥2)个长为4的圈，其顶点集合v(Ci)={vi1,vi2,vi3,vi4}，把Ci和Ci+1中的顶点vij和vi+1,j间连一条边(i=1,2,…,n-1；j=1，2，3，4)，所得图记为Z4,n.那么，Z4,n是优美图.

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

f(vij)=i-1,

f(vij)=4(2n-1)-2(i-1)-2,

f(vij)=(3n-2)-(i-1),

f(vij)=(3n-1)+2(i-1)-1,

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

定理2 设C1,C2,…,Cn是n(n≥2)个长为4的圈，其顶点集合v(Ci)={vi1,vi2,vi3,vi4}，把Ci和Ci+1中的顶点vij和vi+1,j间连一条边(i=1,2,…,n-1；j=1，2，3，4)，所得图记为Z4,n.那么，Z4,n是奇优美图.

证明图Z4,n中，|V(Z4,n)|=4n,|E(Z4,n)|=4(2n-1)，.给出Z4,n各顶点标号f如下：

f(vij)=2(i-1),

f(vij)=8(2n-1)-4(i-1)-1,

f(vij)=2(3n-2)-2(i-1),

f(vij)=2(3n-1)+4(i-1)-1,

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

定理3 设C1,C2,…,Cn是n(n≥2)个长为4的圈，其顶点集合v(Ci)={vi1,vi2,vi3,vi4}，把Ci和Ci+1中的顶点vij和vi+1,j间连一条边(i=1,2,…,n-1；j=1，2，3，4)，所得图记为Z4,n.那么，Z4,n是k-优美图.

证明图Z4,n中，|V(Z4,n)|=4n,|E(Z4,n)|=4(2n-1)，.给出Z4,n各顶点标号f如下：

f(vij)=i-1,

f(vij)=k+4(2n-1)-2(i-1)-2,

f(vij)=(3n-2)-(i-1),

f(vij)=k+(3n-1)+2(i-1)-1,

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

定理4 设C1,C2,…,Cn是n(n≥2)个长为4的圈，其顶点集合v(Ci)={vi1,vi2,vi3,vi4}，把Ci和Ci+1中的顶点vij和vi+1,j间连一条边(i=1,2,…,n-1；j=1，2，3，4)，所得图记为Z4,n.那么，Z4,n是奇强协调图.

证明图Z4,n中，|V(Z4,n)|=4n,|E(Z4,n)|=4(2n-1)，.给出Z4,n各顶点标号f如下：

f(vij)=4(i-1),

f(vij)=2(i-1),

f(vij)=4(2n-1)-2-4(i-1),

f(vij)=4(2n-1)+1-2(i-1),

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

定理5 设C1,C2,…,Cn是n(n≥2)个长为4的圈，其顶点集合v(Ci)={vi1,vi2,vi3,vi4}，把Ci和Ci+1中的顶点vij和vi+1,j间连一条边(i=1,2,…,n-1；j=1，2，3，4)，所得图记为Z4,n.那么，Z4,n是k-强协调图.

证明图Z4,n中，|V(Z4,n)|=4n,|E(Z4,n)|=4(2n-1)，.给出Z4,n各顶点标号f如下：

f(vij)=2(i-1),

f(vij)=k+(i-1),

f(vij)=2(2n-1)-1-2(i-1),

f(vij)=k+2(2n-1)-(i-1),

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