關(guān)于太陽圖奇偶可分的魔幻標號

王亞茹， 姚 兵，2

(1.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅 蘭州 730070；2.蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

關(guān)于太陽圖奇偶可分的魔幻標號

王亞茹1， 姚 兵1，2

(1.西北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅 蘭州 730070；2.蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

對一類圈上有奇數(shù)個節(jié)點的太陽圖進行邊魔幻優(yōu)美標號研究，得到了其超級邊魔幻優(yōu)美標號和邊魔幻全標號，并對特殊的廣義太陽圖確定了其邊魔幻優(yōu)美標號和邊魔幻全標號.提出了一種新的邊魔幻優(yōu)美標號和邊魔幻全標號，分別稱為奇偶可分的邊魔幻優(yōu)美標號和奇偶可分的邊魔幻全標號，指出一類特殊太陽圖和廣義太陽圖具有奇偶可分的邊魔幻優(yōu)美標號和奇偶可分的邊魔幻全標號.

太陽圖；邊魔幻優(yōu)美標號；超級邊魔幻優(yōu)美標號；邊魔幻全標號

0 引言

生活中有各種各樣的網(wǎng)絡(luò)，每種網(wǎng)絡(luò)都可以建立相應(yīng)的模型，其中環(huán)形網(wǎng)絡(luò)在網(wǎng)絡(luò)設(shè)計和建設(shè)中有著特殊的地位.這類網(wǎng)絡(luò)可以細化工作與分塊管理，具有資源利用率和共享率高、投資費用較低、穩(wěn)定性好等特點，所以在工作、生活中應(yīng)用較為廣泛.對環(huán)形網(wǎng)絡(luò)的研究，通常是將其轉(zhuǎn)化成圖論中的太陽圖，將太陽圖中圈上的每一個節(jié)點當作一個服務(wù)器，與圈所連接的節(jié)點看作是客戶計算機.

圖的標號是很多學(xué)科研究的重要手段之一.圖的標號有很多，例如優(yōu)美標號、奇優(yōu)美標號、幸福標號、魔幻類標號等.[1]1963年，Sedl首次定義了圖的魔幻標號.根據(jù)Bloom和Golomb的結(jié)果，Wallis[3]提出了邊魔幻全標號的概念.本文的邊魔幻優(yōu)美標號和超級邊魔幻優(yōu)美標號是由Marimuthu等[4-5]提出的.其他關(guān)于魔幻類的標號可參見文獻[1，6-11].

本文定義的新標號如下：

(1) 若f為圖G的一個邊魔幻優(yōu)美標號，且f(V(G))={1，3，5，…，2L+1}，f(E(G))={2，4，6，…，2M}，則稱f為圖G的一個奇偶可分的邊魔幻優(yōu)美標號；

(2) 若f為圖G的一個邊魔幻全標號，且有f(V(G))={1，3，5，…，2L+1}，f(E(G))={2，4，6，…，2M}，則稱f為圖G的一個奇偶可分的邊魔幻全標號.

1 預(yù)備知識

本文涉及的圖均為簡單的無向圖.一個(p，q)-圖有p個頂點和q條邊.為了敘述簡便，記號[m，n]表示非負整數(shù)集合{m，m+1，m+2，…，n}，其中m和n均為整數(shù)，且滿足0≤m

定義1設(shè)Cn=a1a2a3…ana1是一個長度為n≥3的圈.給Cn的每個頂點ai(i∈[1，n])用一條邊連接一個新頂點yi，所得到的圖稱為太陽圖，記為SCn,如圖1所示.Cn的每個頂點ai(i∈[1，n])連ki個新頂點ai，1ai，2ai，3…ai，ki，所得到的圖稱為廣義太陽圖，記為GSCn(允許某些ki=0).

本文研究了n為奇數(shù)的太陽圖奇偶可分的邊魔幻優(yōu)美標號和奇偶可分的邊魔幻全標號.為了方便，本文中稱此類太陽圖為奇圈的太陽圖.

定義2設(shè)Cn=a1a2a3…ana1是一個長度為奇數(shù)n≥3的圈.給Cn的每個頂點ai(i∈[1，n])用m條邊連接m個新頂點y(i-1)m+j(j∈[1，m])，所得到的圖稱為奇圈的特殊太陽圖，記為GSCn，m，如圖2所示.

記f(V(G))={f(x)|x∈V(G)}，f(E(G))={f(uv)|uv∈E(G)}.

圖1 太陽圖

圖2 奇圈的特殊太陽圖

定義3[3]設(shè)G是(p，q)-圖.若存在常數(shù)k和雙射f：V(G)∪E(G)→{1，2，3，…，p+q}，使對G的任意一條邊uv，總有 |f(u)+f(v)-f(uv)|=k，則稱f為圖G的一個邊魔幻優(yōu)美標號，k為魔幻常數(shù).此外，若f(V(G))={1，2，3，…，p}，則稱f為圖G的一個超級邊魔幻優(yōu)美標號.

定義4[1]設(shè)G是(p，q)-圖.若存在常數(shù)k和雙射f：V(G)∪E(G)→{1，2，3，…，p+q}， 使對G的任意一條邊uv，總有f(u)+f(v)+f(uv)=k，則稱f為圖G的一個邊魔幻全標號，k為魔幻常數(shù).

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

定理1奇圈的太陽圖具有奇偶可分的邊魔幻優(yōu)美標號.

證明采用定義1中的記號，頂點數(shù)p=2n，邊數(shù)q=2n.記頂點集為V(SCn)={a1，a2，a3，…，an-1，an，y1，y2，…，yn-1，yn}，邊集為E(SCn)={a1a2，a2a3，a3a4，…，an-1an，ana1，a1y1，a2y2，…，an-1yn-1，anyn}.定義奇圈的太陽圖SCn的標號f如下：

f(ai)=i，i=1，3，5，…，n-2，n；f(ai)=n+i，i=2，4，6，…，n-3，n-1；f(yi)=4n-2i-1，i=1，2，3，…，n-1；f(yn)=4n-1；f(aiaj)=2i+2，i=1，2，3，…，n-1，j=i+1；f(ana1)=2；f(aiyi)=3n-i，i=1，3，5，…，n-4，n-2；f(aiyi)=4n-i，i=2，4，6，…，n-3，n-1；f(anyn)=4n.

由上面的標號可知：f(V(SCn))={1，3，5，7，…，4n-3，4n-1}，f(E(SCn))={2，4，6，8，…，4n-2，4n}.由此可得V(SCn)∪E(SCn)→{1，2，3，…，4n}.當i=1，3，5，7，…，n-2時，j=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號，得

|f(ai)+f(aj)-f(aiaj)|=|i+(n+j)-(2i+2)|=|i+n+i+1-2i-2|=|n-1|=n-1；

當i=2，4，6，8，…，n-1時，j=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號，得

|f(ai)+f(aj)-f(aiaj)|=|(n+i)+j-(2i+2)|=|n+i+i+1-2i-2|=|n-1|=n-1，

|f(an)+f(a1)-f(ana1)|=|n+1-2|=|n-1|=n-1；

當i=1，3，5，7，…，n-2時，計算太陽的光芒aiyi上的標號，得

|f(ai)+f(yi)-f(aiyi)|=|i+(4n-2i-1)-(3n-i)|=|i+4n-2i-1-3n+i|=|n-1|=n-1;

當i=2，4，6，8，…，n-1時，計算太陽的光芒aiyi上的標號，得

|f(ai)+f(yi)-f(aiyi)|=|(n+i)+(4n-2i-1)-(4n-i)|=
|n+i+4n-2i-1-4n+i|=|n-1|=n-1，

|f(an)+f(yn)-f(anyn)|=|n+(4n-1)-4n|=|n+4n-1-4n|=|n-1|=n-1.

圖3 定理1當魔幻常數(shù)k=4的情形

綜上，f是太陽圖SCn一個奇偶可分的邊魔幻優(yōu)美標號.

圖3給出了定理1在魔幻常數(shù)k=4時的情形.

定理2奇圈的太陽圖具有超級邊魔幻優(yōu)美標號.

證明采用定義1中的記號.由定理1知f是奇圈太陽圖SCn的一個奇偶可分的邊魔幻優(yōu)美標號，下面在此基礎(chǔ)上對奇圈太陽圖SCn定義一個新的標號g為：g(ai)=f(ai)+1=i+1，i=1，3，5，…，n-2，n；g(ai)=f(ai)+1=n+i+1，i=2，4，6，…，n-3，n-1；g(yi)=f(yi)-2n=2n-2i-1，i=1，2，3，…，n-1；g(yn)=f(yn)-2n=2n-1；g(aiaj)=f(aiaj)+2n=2n+2i+2，i=1，2，3，…，n-1，j=i+1；g(ana1)=f(ana1)+2n=2n+2；g(aiyi)=f(aiyi)-1=3n-i-1，i=1，3，5，…，n-4，n-2；g(aiyi)=f(aiyi)-1=4n-i-1，i=2，4，6，…，n-3，n-1；g(anyn)=f(anyn)-1=4n-1.

由上面規(guī)定的標號可知：g(V(SCn))={1，2，3，4，…，2n}，g(E(SCn))={2n+1，2n+2，2n+3，2n+4，…，4n}.由此可得V(SCn)∪E(SCn)→{1，2，3，…，4n}.當i=1，3，5，7，…，n-2時，j=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號，得

|g(ai)+g(aj)-g(aiaj)|=|(i+1)+(n+j+1)-(2n+2i+2)|=
|i+1+n+i+1+1-2n-2i-2|=|1-n|=n-1;

(1)

當i=2，4，6，8，…，n-1時，j=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號，類似有(1)式成立；當i=1，3，5，7，…，n-2和i=2，4，6，8，…，n-1時，計算太陽的光芒aiyi上的標號，仍有(1)式成立.

圖4 定理2當魔幻常數(shù)k=4的情形

綜上，標號g是太陽圖SCn的一個超級邊魔幻優(yōu)美標號.

圖4給出了定理2當魔幻常數(shù)k=4的情形.

定理3奇圈的太陽圖具有奇偶可分的邊魔幻全標號.

證明采用定義1中的記號.由定理1知f是奇圈的太陽圖SCn的一個奇偶可分的邊魔幻優(yōu)美標號.下面利用標號f定義奇圈的太陽圖SCn的一個新標號h為：h(ai)=f(ai)=i，i=1，3，5，…，n-2，n；h(ai)=f(ai)=n+i，i=2，4，6，…，n-3，n-1；h(yi)=f(yi)=4n-2i-1，i=1，2，3，…，n-1；h(yn)=f(yn)=4n-1；h(aiaj)=4n-f(aiaj)+2=4n-2i，i=1，2，3，…，n-1，j=i+1；h(ana1)=4n-f(ana1)+2=4n；h(aiyi)=4n-f(aiyi)+2=n+i+2，i=1，3，5，…，n-4，n-2；h(aiyi)=4n-f(aiyi)+2=i+2，i=2，4，6，…，n-3，n-1；h(anyn)=4n-f(anyn)+2=2.

由上面標號的定義可知：h(V(SCn))={1，3，5，7，…，4n-3，4n-1}，h(E(SCn))={2，4，6，8，…，4n-2，4n}.由此可得V(SCn)∪E(SCn)→{1，2，3，…，4n}.

當i=1，3，5，7，…，n-2時，j=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號為

h(ai)+h(aj)+h(aiaj)=i+(n+j)+(4n-2i)=i+n+i+1+4n-2i=5n+1;

當i=2，4，6，8，…，n-1時，j=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號為

h(ai)+h(aj)+h(aiaj)=(n+i)+j+(4n-2i)=n+i+i+1+4n-2i=5n+1，

h(an)+h(a1)+h(ana1)=n+1+4n=5n+1;

(2)

當i=1，3，5，7，…，n-2和i=2，4，6，8，…，n-1時，計算太陽的光芒aiyi上的標號后仍有(2)式成立.

圖5 定理3當魔幻常數(shù)k=26的情形

綜上，h是太陽圖SCn的一個奇偶可分的邊魔幻全標號.

圖5給出了定理3當魔幻常數(shù)k=26時的情形.

將上面這種特殊的奇圈的太陽圖推廣，即在圈上的每個節(jié)點上添加m個葉子，得到奇圈的特殊太陽圖.

定理4奇圈的特殊太陽圖具有奇偶可分的邊魔幻優(yōu)美標號.

證明沿用定義2中的記號，且頂點數(shù)p=n(m+1)，邊數(shù)q=n(m+1).記頂點集為V(GSCn，m)={a1，a2，a3，…，an，y1，y2，…，ym，…，y(i-1)m+j，…，y(n-1)m+1，…，ynm}，邊集為E(GSCn，m)={a1a2，a2a3，a3a4，…，ana1，a1y1，…，a1ym，…，any(n-1)m+1，…，anynm}.定義奇圈的特殊太陽圖GSCn，m的一個標號f為：f(ai)=i，i=1，3，5，…，n-2，n；f(ai)=n+i，i=2，4，6，…，n-3，n-1；f(y(i-1)m+j)=2(j+1)n-2i-1，i=1，2，3，…，n-1，j=1，2，3，…，m；f(y(n-1)m+j)=2(j+1)n-1，j=1，2，3，…，m；f(aiak)=2i+2，i=1，2，3，…，n-1，k=i+1；f(ana1)=2；f(aiy(i-1)m+j)=(2j+1)n-i，i=1，3，5，…，n-4，n-2，j=1，2，3，…，m；f(aiy(i-1)m+j)=2(j+1)n-i，i=2，4，6，…，n-3，n-1，j=1，2，3，…，m；f(any(n-1)m+j)=2(j+1)n，j=1，2，3，…，m.

由上面的標號性質(zhì)可知：f(V(GSCn，m))={1，3，5，7，…，2n(m+1)-3，2n(m+1)-1}，f(E(GSCn，m))={2，4，6，8，…，2n(m+1)-2，2n(m+1)}.由此得V(GSCn，m)∪E(GSCm，m)→{1，2，3，…，2n(m+1)}.當i=1，3，5，…，n-4，n-2時，k=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號，得

|f(ai)+f(ak)-f(aiak)|=|i+(n+k)-(2i+2)|=|i+n+i+1-2i-2|=|n-1|=n-1;

(3)

當i=2，4，6，…，n-3，n-1時，k=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號，仍有(3)式成立；當i=1，3，5，…，n-4，n-2時，j=1，2，3，…，m，計算太陽的光芒aiy(i-1)m+j上的標號，得

|f(ai)+f(y(i-1)m+j)-f(aiy(i-1)m+j)|=|i+[2(j+1)n-2i-1]-[(2j+1)n-i]|=|n-1|=n-1;

當i=2，4，6，…，n-3，n-1時，j=1，2，3，…，m，計算太陽的光芒aiy(i-1)m+j上的標號，得

|f(ai)+f(y(i-1)m+j)-f(aiy(i-1)m+j)|=n-1，

|f(an)+f(y(n-1)m+j)-f(any(n-1)m+j)|=|n+[2(j+1)n-1]-2(j+1)n|=|n-1|=n-1.

圖6 定理4當魔幻常數(shù)k=4的情形

綜上，f是奇圈特殊太陽圖GSCn，m的一個奇偶可分的邊魔幻優(yōu)美標號.

圖6給出了定理4當魔幻常數(shù)k=4的情形.

定理5奇圈的特殊太陽圖具有奇偶可分的邊魔幻全標號.

證明由定理4知f是奇圈的特殊太陽圖GSCn，m的一個奇偶可分的邊魔幻優(yōu)美標號.下面在f的基礎(chǔ)上對奇圈特殊太陽圖GSCn，m定義一個新的標號h為：h(ai)=f(ai)=i，i=1，3，5，…，n-2，n；h(ai)=f(ai)=n+i，i=2，4，6，…，n-3，n-1；h(y(i-1)m+j)=f(y(i-1)m+j)=2(j+1)n-2i-1，i=1，2，3，…，n-1，j=1，2，3，…，m；h(y(n-1)m+j)=f(y(n-1)m+j)=2(j+1)n-1，j=1，2，3，…，m；h(aiak)=2n(m+1)-f(aiak)+2=2n(m+1)-2i，i=1，2，3，…，n-1，k=i+1；h(ana1)=2n(m+1)-f(ana1)+2=2n(m+1)；h(aiy(i-1)m+j)=2n(m+1)-f(aiy(i-1)m+j)+2=n(2m-2j+1)+i+2，i=1，3，5，…，n-4，n-2，j=1，2，3，…，m；h(aiy(i-1)m+j)=2n(m+1)-f(aiy(i-1)m+j)+2=2n(m-j)+i+2，i=2，4，6，…，n-3，n-1，j=1，2，3，…，m；h(any(n-1)m+j)=2n(m+1)-f(any(n-1)m+j)+2=2n(m-j)+2，j=1，2，3，…，m.

由上面規(guī)定的標號可知：h(V(GSCn，m))={1，3，5，7，…，2n(m+1)-3，2n(m+1)-1}，h(E(GSCn，m))={2，4，6，8，…，2n(m+1)-2，2n(m+1)}.由此可得V(GSCn，m)∪E(GSCn，m)→{1，2，3，…，2n(m+1)}.當i=1，3，5，…，n-4，n-2時，k=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號

h(ai)+h(ak)+h(aiak)=i+(n+k)+[2n(m+1)-2i]=2n(m+1)+n+1;

當i=2，4，6，…，n-3，n-1時，k=i+1，計算圈Cn上的2個相鄰頂點ai，ai+1及其邊aiai+1的標號

h(ai)+h(ak)+h(aiak)=(n+i)+k+[2n(m+1)-2i]=2n(m+1)+n+1，

h(an)+h(a1)+h(ana1)=n+1+2n(m+1)=2n(m+1)+n+1;

當i=1，3，5，…，n-4，n-2時，j=1，2，3，…，m，計算太陽的光芒aiy(i-1)m+j上的標號

圖7 定理5當魔幻常數(shù)k=36的情形

當i=2，4，6，…，n-3，n-1時，j=1，2，3，…，m，計算太陽的光芒aiy(i-1)m+j上的標號

h(ai)+h(y(i-1)m+j)+h(aiy(i-1)m+j)=2n(m+1)+n+1，

h(an)+h(y(n-1)m+j)+h(any(n-1)m+j)=2n(m+1)+n+1.

綜上，h是奇圈特殊太陽圖GSCn，m的一個奇偶可分的邊魔幻全標號.

圖7給出了定理5當魔幻常數(shù)k=36時的情形.

[1] GALLIAN J A.A dynamic survey of graph labelling[J].The Electronic Journal of Combinatorics，2009，14：211-219.

[2] SEDLACEK J.Problem 27[M]//Theory of Graphs and its Applications.Praha： Academia，1963：163-169.

[3] WALLIS W D.Magic Graphs[M].Berlin： Birkh?user，2001：1031-1059.

[4] MARIMUTHU G.Super edge magic graceful labeling of generalized petersen garphs[J].Electronic Notes in Discrete Mathematics，2015，48：235-241.

[5] MARIMUTHU G，BALAKRISHNAN M.Super edge magic graceful graphs[J].Inform Sci，2003，287：245-255.

[6] 姚明，姚兵，謝建民.關(guān)于圖的k-魔幻標號的若干結(jié)果[J].甘肅科學(xué)學(xué)報，2010，22(1)：1-6.

[7] 王宏宇，姚兵，楊超.一類特殊對稱圖的邊魔幻性[J].四川師范大學(xué)學(xué)報(自然科學(xué)版)，2013，36(1)：28-33.

[8] 王宏宇，姚兵，楊超.可拆分樹的邊魔幻全標號性[J].山東大學(xué)學(xué)報(理學(xué)版)，2014，49(4)：29-37.

[9] WANG H Y，YAO B，YANG C，et al.Edge-magic total labellings of some network models[J].Applied Mechanics and Materials，2013，347：2752-2757.

[10] YAO B，CHEN X E，YAO M，et al.On(k，λ)-magically total labeling of graphs[J].Journal of Combinatorial Mathematics and Combinatorial Computing，2013，87：237-253

[11] WANG H Y，YAO B，YAO M.Generalized edge-magic total labellings of models from researching networks[J].Information Sciences，2014，279：460-467.

Onthemagiclabellingdividedintoparityofsun-graphs

WANG Ya-ru1，YAO Bing1，2

(1.College of Mathematics and Statistics，Northwest Normal University，Lanzhou 730070，China；2.School of Electronic and Information Engineering，Lanzhou Jiaotong University，Lanzhou 730070，China)

Edge magic graceful labelling of a class of sun-graph that has an odd node number of circle is studied，further its super edge magic graceful labelling and edge-magic total labelling.Special sun-graph having edge magic graceful labelling and edge-magic total labelling is constructed.It proposes a new edge magic graceful labelling and edge-magic total labelling，called edge-magic graceful labelling divided into parity and edge-magic total labelling divided into parity.All

，a kind of special sun-graph and generalized sun-graph with edge-magic graceful labelling divided into parity and edge-magic total labelling divided into parity.

sun-graph；edge-magic graceful labelling；super edge magic graceful labelling；edge-magic total labelling

1000-1832(2017)04-0010-05

10.16163/j.cnki.22-1123/n.2017.04.003

2016-06-20

國家自然科學(xué)基金資助項目(61163054，61363060，61662066).

王亞茹(1994—)，女，本科生，主要從事圖著色與標號研究；通信作者：姚兵(1956—)，男，教授，主要從事圖著色與標號、復(fù)雜網(wǎng)絡(luò)及優(yōu)化研究.

O 157.5學(xué)科代碼110·7470

A

(責任編輯：李亞軍)