嚴謙泰

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

1 引言

優(yōu)美圖由于其有趣性及較好的應用價值和研究前景，其研究十分活躍。最近十幾年來，國內外取得不少優(yōu)美圖的研究成果[1]，它們也被用于許多領域[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é)調標號問題是圖論中的一個十分有趣的研究課題,自1982年，D·Fank Hsu引入圖的強協(xié)調標號，已有許多這方面的結果. 之后，作者提出了奇強協(xié)調圖和k-強協(xié)調圖的概念，拓寬強協(xié)調標號問題的研究.

定義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]設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é)調圖，f稱為G的強協(xié)調標號.

定義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是奇強協(xié)調圖，f稱為G的奇強協(xié)調標號或奇強協(xié)調值.顯然f導出了一個E(G)與{1,3,5,…,2|E|-1}的一個一一對應.

本文研究了一類網格圖類圖的優(yōu)美性和強協(xié)調性.未加說明的術語和記號見文獻[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是優(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 設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 設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 設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é)調圖.

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

定理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-強協(xié)調圖.

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