網(wǎng)格圖Z4，n的優(yōu)美標號和強協(xié)調(diào)標號

嚴謙泰

(安陽師范學院 數(shù)學與統(tǒng)計學院，河南 安陽 455000)

1 引言

優(yōu)美圖由于其有趣性及較好的應(yīng)用價值和研究前景，其研究十分活躍。最近十幾年來，國內(nèi)外取得不少優(yōu)美圖的研究成果[1]，它們也被用于許多領(lǐng)域[2].它的研究始于1963年G.Ringel的一個猜想[3]和1966年A.Rosa的一篇論文[4].1972年，S.W.Golomb明確給出了優(yōu)美圖的定義[5].之后，Gnanajoethi又提出了：每棵樹都是奇優(yōu)美的[6]，開始了奇優(yōu)美圖的研究。但由于缺少系統(tǒng)和有力的工具，到底滿足什么條件的圖是優(yōu)美圖，即表征優(yōu)美圖仍是一個世界難題，因此至今只能對一些特殊圖類研究其優(yōu)美性. 圖的強協(xié)調(diào)標號問題是圖論中的一個十分有趣的研究課題,自1982年，D·Fank Hsu引入圖的強協(xié)調(diào)標號，已有許多這方面的結(jié)果. 之后，作者提出了奇強協(xié)調(diào)圖和k-強協(xié)調(diào)圖的概念，拓寬強協(xié)調(diào)標號問題的研究.

定義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為優(yōu)美圖，稱f為G的優(yōu)美標號.

定義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為奇優(yōu)美圖，稱f為G的奇優(yōu)美標號.

定義3[8]設(shè)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是強協(xié)調(diào)圖，f稱為G的強協(xié)調(diào)標號.

定義4[10]設(shè)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是奇強協(xié)調(diào)圖，f稱為G的奇強協(xié)調(diào)標號或奇強協(xié)調(diào)值.顯然f導(dǎo)出了一個E(G)與{1,3,5,…,2|E|-1}的一個一一對應(yīng).

本文研究了一類網(wǎng)格圖類圖的優(yōu)美性和強協(xié)調(diào)性.未加說明的術(shù)語和記號見文獻[2].

2 主要結(jié)論及證明

定理1 設(shè)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是優(yōu)美圖.

證明給出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的一個優(yōu)美標號，所以Z4,n是優(yōu)美圖

定理2 設(shè)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是奇優(yōu)美圖.

證明圖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的一個奇優(yōu)美標號，所以Z4,n是奇優(yōu)美圖.

定理3 設(shè)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-優(yōu)美圖.

證明圖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-奇優(yōu)美標號，所以Z4,n是k-優(yōu)美圖.

定理4 設(shè)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是奇強協(xié)調(diào)圖.

證明圖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的一個奇強協(xié)調(diào)標號，所以Z4,n是奇強協(xié)調(diào)圖.

定理5 設(shè)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-強協(xié)調(diào)圖.

證明圖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-強協(xié)調(diào)標號，所以Z4,n是k-強協(xié)調(diào)圖.