王亚茹， 姚 兵，2

(1.西北师范大学数学与统计学院，甘肃 兰州 730070；2.兰州交通大学电子与信息工程学院，甘肃 兰州 730070)

关于太阳图奇偶可分的魔幻标号

王亚茹1， 姚 兵1，2

(1.西北师范大学数学与统计学院，甘肃 兰州 730070；2.兰州交通大学电子与信息工程学院，甘肃 兰州 730070)

对一类圈上有奇数个节点的太阳图进行边魔幻优美标号研究，得到了其超级边魔幻优美标号和边魔幻全标号，并对特殊的广义太阳图确定了其边魔幻优美标号和边魔幻全标号.提出了一种新的边魔幻优美标号和边魔幻全标号，分别称为奇偶可分的边魔幻优美标号和奇偶可分的边魔幻全标号，指出一类特殊太阳图和广义太阳图具有奇偶可分的边魔幻优美标号和奇偶可分的边魔幻全标号.

太阳图；边魔幻优美标号；超级边魔幻优美标号；边魔幻全标号

0 引言

生活中有各种各样的网络，每种网络都可以建立相应的模型，其中环形网络在网络设计和建设中有着特殊的地位.这类网络可以细化工作与分块管理，具有资源利用率和共享率高、投资费用较低、稳定性好等特点，所以在工作、生活中应用较为广泛.对环形网络的研究，通常是将其转化成图论中的太阳图，将太阳图中圈上的每一个节点当作一个服务器，与圈所连接的节点看作是客户计算机.

图的标号是很多学科研究的重要手段之一.图的标号有很多，例如优美标号、奇优美标号、幸福标号、魔幻类标号等.[1]1963年，Sedl首次定义了图的魔幻标号.根据Bloom和Golomb的结果，Wallis[3]提出了边魔幻全标号的概念.本文的边魔幻优美标号和超级边魔幻优美标号是由Marimuthu等[4-5]提出的.其他关于魔幻类的标号可参见文献[1，6-11].

本文定义的新标号如下：

(1) 若f为图G的一个边魔幻优美标号，且f(V(G))={1，3，5，…，2L+1}，f(E(G))={2，4，6，…，2M}，则称f为图G的一个奇偶可分的边魔幻优美标号；

(2) 若f为图G的一个边魔幻全标号，且有f(V(G))={1，3，5，…，2L+1}，f(E(G))={2，4，6，…，2M}，则称f为图G的一个奇偶可分的边魔幻全标号.

1 预备知识

本文涉及的图均为简单的无向图.一个(p，q)-图有p个顶点和q条边.为了叙述简便，记号[m，n]表示非负整数集合{m，m+1，m+2，…，n}，其中m和n均为整数，且满足0≤m

定义1设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为奇数的太阳图奇偶可分的边魔幻优美标号和奇偶可分的边魔幻全标号.为了方便，本文中称此类太阳图为奇圈的太阳图.

定义2设Cn=a1a2a3…ana1是一个长度为奇数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]设G是(p，q)-图.若存在常数k和双射f：V(G)∪E(G)→{1，2，3，…，p+q}，使对G的任意一条边uv，总有 |f(u)+f(v)-f(uv)|=k，则称f为图G的一个边魔幻优美标号，k为魔幻常数.此外，若f(V(G))={1，2，3，…，p}，则称f为图G的一个超级边魔幻优美标号.

定义4[1]设G是(p，q)-图.若存在常数k和双射f：V(G)∪E(G)→{1，2，3，…，p+q}， 使对G的任意一条边uv，总有f(u)+f(v)+f(uv)=k，则称f为图G的一个边魔幻全标号，k为魔幻常数.

2 主要结论及其证明

定理1奇圈的太阳图具有奇偶可分的边魔幻优美标号.

证明采用定义1中的记号，顶点数p=2n，边数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当魔幻常数k=4的情形

综上，f是太阳图SCn一个奇偶可分的边魔幻优美标号.

图3给出了定理1在魔幻常数k=4时的情形.

定理2奇圈的太阳图具有超级边魔幻优美标号.

证明采用定义1中的记号.由定理1知f是奇圈太阳图SCn的一个奇偶可分的边魔幻优美标号，下面在此基础上对奇圈太阳图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.

由上面规定的标号可知：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当魔幻常数k=4的情形

综上，标号g是太阳图SCn的一个超级边魔幻优美标号.

图4给出了定理2当魔幻常数k=4的情形.

定理3奇圈的太阳图具有奇偶可分的边魔幻全标号.

证明采用定义1中的记号.由定理1知f是奇圈的太阳图SCn的一个奇偶可分的边魔幻优美标号.下面利用标号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当魔幻常数k=26的情形

综上，h是太阳图SCn的一个奇偶可分的边魔幻全标号.

图5给出了定理3当魔幻常数k=26时的情形.

将上面这种特殊的奇圈的太阳图推广，即在圈上的每个节点上添加m个叶子，得到奇圈的特殊太阳图.

定理4奇圈的特殊太阳图具有奇偶可分的边魔幻优美标号.

证明沿用定义2中的记号，且顶点数p=n(m+1)，边数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.

由上面的标号性质可知：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当魔幻常数k=4的情形

综上，f是奇圈特殊太阳图GSCn，m的一个奇偶可分的边魔幻优美标号.

图6给出了定理4当魔幻常数k=4的情形.

定理5奇圈的特殊太阳图具有奇偶可分的边魔幻全标号.

证明由定理4知f是奇圈的特殊太阳图GSCn，m的一个奇偶可分的边魔幻优美标号.下面在f的基础上对奇圈特殊太阳图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.

由上面规定的标号可知：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当魔幻常数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当魔幻常数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] 姚明，姚兵，谢建民.关于图的k-魔幻标号的若干结果[J].甘肃科学学报，2010，22(1)：1-6.

[7] 王宏宇，姚兵，杨超.一类特殊对称图的边魔幻性[J].四川师范大学学报(自然科学版)，2013，36(1)：28-33.

[8] 王宏宇，姚兵，杨超.可拆分树的边魔幻全标号性[J].山东大学学报(理学版)，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

国家自然科学基金资助项目(61163054，61363060，61662066).

王亚茹(1994—)，女，本科生，主要从事图着色与标号研究；通信作者：姚兵(1956—)，男，教授，主要从事图着色与标号、复杂网络及优化研究.

O 157.5学科代码110·7470

A

(责任编辑：李亚军)