一类平面图I(n)的超边幻和标号及其算法

刘家保，王 林

(安徽新华学院 a.公共课教学部;b.计算机科学与技术系，合肥 230088)

一类平面图I(n)的超边幻和标号及其算法

刘家保a，王 林b

(安徽新华学院 a.公共课教学部;b.计算机科学与技术系，合肥 230088)

探索和研究了一类新平面图的超边幻和标号问题，运用算法设计与分析中的分支限界理论和思想设计了各顶点和边的超边幻和标号算法，给出并严格证明了此类新的平面图是超边幻和图等结论。

超边幻和标号;超边幻和图;平面图类

0 引言

图标号问题是图论中的一类重要研究课题，起始于上世纪六十年代A·Rosa的著名优美树猜想，其背景来源于众多实际问题，应用范围广泛深入众多领域。幻类型标号主要有边幻和标号、超边幻和标号、超点幻和标号反边幻和标号等，是受数论中的幻方启发提出的。超边幻和标号问题就是一种对图的标号问题，具有超边幻和标号的图被称为超边幻和图。Kotzig和Rosa［1］在1970年给出了边幻和标号的定义，Enomoto［2］等人给出了超边幻和标号的定义。超边幻和标号是其中一类条件非常严格的标号，与序列标号、调和标号、平衡标号和亲切标号等有着紧密的联系，研究超边幻和标号问题有助于研究其它类型的图标号问题。

1 基本概念

定义1对于一个给定的简单图G=(V，E)，如果G=(V，E)是有p个顶点q条边的图.假设G的顶点和边由1，2，…，p+q所标号，且 L:V∪E→{1，2，…，p+q}是一个双射，如果对所有的边 xy，L(x)+L(y)+L(xy)=C是个常量，则称图G是边幻和图(edge-magic total graph)，称L为G的边幻和标号(edge-magic total labeling)。

定义2设L为图G(V，E)的边幻和标号，如果顶点标号满足:L(V(G))={1，2，Λ，|V(G)|}，则称L为图G的超边幻和标号(super edge-magic total labeling)，图G称为具有超边幻和标号L的超边幻和图(super edge-magic total labeling)。

定义3对于一类平面图I(n)，其顶点集和边集分别为V(I(n))和E(I(n))，如果图I(n)是具有n+4个顶点和2n+5条边的图，各顶点和边均由集合A={1，2，…，3n+9}中的元素所标号，且存在一个双射函数L:V(I(n))∪E(I(n))→{1，2，…，3n+9}，则图I(n)是表示满足以下条件的图类:

(1)顶点集为 V(I(n))={u1，x，u2，y}∪{v1，v2，…，vn};

(2)边集为 E(I(n))={u1x，xu2，u2y，yu1，u1u2}∪{xvi|i=1，2，…，n}∪{viy|i=1，2，…，n}.

2 主要结果

设平面图I(n)=(V，E)，其顶点集和边集分别为V(I(n))和E(I(n))，则顶点数|V(I(n))|=n+4，边数|E(I(n))|=2n+5。

由于图I(n)存在一个双射函数L:V(I(n))→{1，2，…，n+4}使得k={L(x)+L(y):xy∈E(I(n))}中的元素均为连续整数。在此条件下，L可扩展为图I(n)的超边幻和标号，其中常数C=|V(I(n))|+|E(I(n))|+m，m=min(k)，并且 k={C －(n+5)，C －(n+6)，…，C －(3n+9)}。若 L为图 I(n)的标号，∀xy∈E(I(n))，则边幻常数C为:L(x)+L(xy)+L(y)=3n+12。

定义函数L:V(I(n))∪E(I(n))→{1，2，…，3n+9}，我们给出图I(n)各顶点和边的标号算法如下:

(Ⅰ)图I(n)各顶点标号的算法A为:

(Ⅱ)图I(n)各边标号的算法B为:

定理1对∀n∈N*，一类新的平面图I(n)是超边幻和图。

证明运用算法设计与分析的分支限界策略进行严格的数学证明。

首先，证明L是从顶点集V(I(n))到{1，2，…，n+4}的双射函数。

令 A={L(x)，L(u1)，L(u2)，L(y)，L(vi)|1 ≤i≤n，i∈N*}，则:

A1={L(x)}=1;A2={L(u1)}=2;A3={L(u2)}=n+3;

A4={L(y)}=n+4;A5={i+2|1 ≤i≤n，i∈N*}={3，4，…，n+2}。

则A1∪A2∪A3∪A4∪A5是所有顶点标号的集合，且有:

A1∪A2∪A3∪A4∪A5={1，2，3，4…，n+2，n+3，n+4}={1，2，…，n+4}

由上述可知，所有顶点的标号是各不相同的，所以L是一个从V(I(n))到{1，2，…，n+4}的双射函数。

其次，证明L是从E(I(n))到{n+5，n+6，…，3n+9}的双射函数。

令 B={L(u1x)，L(xu2)，L(yu2)，L(yu1)，L(u1u2)，L(xvi)，L(viy)|1 ≤i≤n，i∈N*}，

则:B1={L(u1x)}=3n+9;B2={L(xu2)}=2n+8;

B3={L(u2y)}=n+5;B4={L(yu1)}=2n+6;B5={L(u1u2)}=2n+7;

B6={L(xvi)|1 ≤i≤n，i∈N*}={3n+8，3n+7，…，2n+9};

B7={L(viy)|1 ≤i≤n，i∈N*}={2n+5，2n+4，…，n+6}.

因此，B=B1∪B2∪B3∪B4∪B5∪B6∪B7是所有边的标号的集合，且有:

B=B1∪B2∪B3∪B4∪B5∪B6∪B7

={3n+9，2n+8，n+5，2n+6，2n+7，3n+8，3n+7，…，2n+9，2n+5，2n+4，…，n+6}={n+5，n+6，…，3n+9}

由上述可知，每条边的标号是各不相同的，且边的标号的集合为:{n+5，n+6，…，3n+9}，所以L是一个从 V(I(n))到{1，2，…，3n+9}的双射函数。

根据超边幻和标号的定义，对∀n∈N*，且图I(n)的n确定，边幻和常数C=3n+12，可以得出结论:图I(n)是超边幻和图。综上所述，定理1得证。

3 结语

图论的超边幻和标号是图标号问题中的一类条件非常严格的标号，由于此类标号与序列标号、调和标号、平衡标号和亲切标号等其它类型的标号有着广泛的联系，研究和解决超边幻和标号问题有助于研究其它图类的标号问题。借助计算机工具，运用算法设计和分析，有助于超边幻和标号算法的探索和超边幻和图结论的证明。

本文运用算法设计与分析中的分支界限策略设计和给出了一类新的平面图I(n)的超边幻和标号算法，得出了I(n)的各顶点和边的超边幻和标号，并对其是超边幻和图给出了严格的数学证明。对于其它的平面图类是否具有超边幻和标号算法和超边幻和图等结论，有待进一步的研究与探索。

［1］ A.Kotzig and A.Rosa.Magic valuations of finite graphs［J］.Canad.Math.Bull，1970(13):451 －461.

［2］ H.Enomoto，A.S.Llado，T.Nakamigawa.Super edge-magic graphs［J］.SUT J.Math，1998(34):105 －109.

［3］ R.M.Figueroa-Centeno，R.Ichishima and F.A.Muntaner-Batle，The place of super edge-magic labelings among other classes of labelings［J］.Discrete Mathematics，2001(231):153 －168.

［4］ 胡红亮.图Cn及其r－冠的新的优美标号［J］.纯粹数学与应用数学，2010，26(3):454－457.

［5］ 陈淑贞，周俊梅.关于联图P1∨Pn的K－强优美性［J］.数学杂志，2010，30(2):357－362.

［6］ 刘家保，潘向峰.轮形图和扇形图的优美性［J］.安徽大学学报:自然科学版，2009，133(4):11－13.

［7］ 严谦泰.积图Pn×Pm的奇优美性和奇强协调性［J］.系统科学与数学，2010，30(3):341－348.

［8］ 魏丽侠，张昆龙.图K1∨Cn的非连通并图的优美性［J］.中山大学学报:自然科学版，2007，46(4):13－16.

［9］ 容青，熊冬春.P2r，b图优美性［J］.系统科学与数学，2010，30(5):203－209.

［10］ 刘家保，张季，聂东明.一类新的联图的优美标号算法［J］.汕头大学学报:自然科学版，2011，26(1):8－10.

The Super Edge-magic Total Labeling and Algorithm of a Class of Ichnographies I(n)

LIU Jia-baoa，WANG Linb

(a.Department of Fundamental Courses;b.Department of Computer Science and Technology，Anhui Xinhua University，Hefei 230088，China)

This paper explores the super edge-magic total labeling of a new class of ichnographies，designs the super edge-magic total labeling algorithm of each vertex and edge by using the branch-and-bound theory and thought in algorithm design and analysis，and gives and strictly proves the conclusion that such a new class of ichnographies are super edge-magic labeling graphs.

super edge-magic total labeling;super edge-magic total graph;a class of ichnographies

O157.5

A

1009－3907(2011)12－0058－02

2011-10-09

安徽省高等学校省级自然科学基金项目(KJ2010B076)

刘家保(1982-)，男，安徽六安人，讲师，硕士，主要从事组合网络方面的研究。

责任编辑:钟 声