梅花图的四种同源标号

姚燕红,常庆龙

(1.安阳师范学院 数学与统计学院,河南 安阳 455000;2.泰兴市教师进修学校,江苏 泰兴 225400)

0 引言

1992年,陆书环给出了梅花图的优美标号[1]。本文巧妙地引进了梅花图的一个称之为“源标号”的辅助标号,经过适当的变换,分别得到了梅花图的下述四种标号:奇优美标号、奇强协调标号、(k,d)-算术标号、k-优美标号。

图1 梅花图

定义2[3]对于(p,q)图G,如果存在一个单射:

使得对一切uv∈E(G),由φ*(uv)=|φ(u)-φ(v)|导出一个双射:

则称G是奇优美图,φ是G的一个奇优美标号,φ*是G的边标号。

定义3[4]对于(p,q)图G,如果存在一个单射:

使得对一切uv∈E(G),由τ*(u,v)=τ(u)+τ(v)导出一个双射:

则称G是奇强协调图,τ是G的一个奇强协调标号。

定义4[5]对于(p,q)图G以及正整数k,d(d不能整除k),如果存在一个单射:

使得对一切uv∈E(G),由h*(uv)=h(u)+h(v)导出一个双射h*:

E(G)→{k,k+d,k+2d,…,k+(q-1)d}

则称G是(k,d)-算术图,h是G的一个(k,d)-算术标号。

定义5[6]对于(p,q)图G以及正整数k,如果存在一个单射:

使得对一切uv∈E(G),由g*(u,v)=|g(u)-g(v)|导出一个双射:

则称G是k-优美图,g是G的一个k-优美标号。

1 四种标号的源标号

为了得到梅花图的下述四种标号:奇优美标号、奇强协调标号、(k,d)-算术标号、k-优美标号,我们定义如下的辅助标号(即源标号)f:

当n=3时

f(x0)=0,f(xi)=13-i(i=1,2,3)

f(yj)=2+j(j=1,2),f(y3)=7

当n≡1(mod2)且n>3时

f(yn)=3n-2

当n≡0(mod2)且n≥2时

不难验证,上述辅助标号有如下几个性质。

性质2记

X={x0,y1,y2,…,yn}

若u,v∈X或u,v∈Y, 则f(u)≠f(v)。

2 主要结果

(1)

当n=3时,(1)为

φ(x0)=0,φ(xi)=25-2i(i=1,2,3)

φ(yj)=4+2j(j=1,2),φ(y3)=14

当n≡0(mod2),且n≥2时,(1)为

当n≡1(mod2)时,且n>3时,(1)为

φ(yn)=6n-4

首先,根据f的性质2, 在X中,f(v)各不相同,所以φ(v)=2f(v)也各不相同;同样在Y中,φ(v)=2f(v)-1也各不相同。 又因为在X中φ(v)是偶数,在Y中φ(v)是奇数,所以X中的顶点标号与Y中的顶点标号也不相同。 又

φ*(uv)=|φ(v)-φ(u)|

=2f(v)-1-2f(u)

=2(f(v)-f(u))-1

由性质1

所以

(2)

当n=3时,(2)为

τ(x0)=0,τ(xi)=2i-1 (i=1,2,3)

τ(yi)=4+2j(j=1,2),τ(y3)=14,

当n≡0(mod2),且n≥2时,(2)为

当n≡1(mod2)时,且n>3时,(2)为

τ(yn)=6n-4

τ*(uv)=τ(u)+τ(v)

=2f(u)+2(4n-f(v))+1

=8n-2(f(v)-f(u))+1

由性质1

所以

(3)

当n=3时,(3)为

h(x0)=0,h(xi)=k+(i-1)d(i=1,2,3)

h(yj)=(2+j)d(j=1,2),h(y3)=7d

当n≡0(mod2),且n≥2时,(3)为

当n≡1(mod2)时,且n>3时,(3)为

h(yn)=(3n-2)d

h*(uv)=h(u)+h(v)

=f(u)d+k+(4n-f(v))d

=k+4nd-(f(v)-f(u))d

由性质1

所以

={k,k+d,k+2d,…,k+(4n-1)d}

(4)

当n=3时,(4)为

g(x0)=0,g(xi)=12-i+k(i=1,2,3)

g(yj)=2+j(j=1,2),g(y3)=7

当n≡0(mod2),且n≥2时,(4)为

当n≡1(mod2)时,且n>3时,(4)为

g(yn)=3n-2

显然,在X和Y中,g(v)各不相同。又因为

g*(uv)=|g(u)-g(v)|

=(f(v)-f(u))+k-1

由性质1

所以