刘家保，王 林

(安徽新华学院 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)的边幻和标号，如果顶点标号……