的边幻和标号算法及超边幻和标号算法

（1.安徽新华学院公共课程部，合肥 230088；2.安徽大学数学科学学院，合肥 230601）

（1.安徽新华学院公共课程部，合肥 230088；2.安徽大学数学科学学院，合肥 230601）

设L为简单无向图G从V(G)∪E(G)→｛1,2,…,l V(G)∪E(G)l｝的一个双射函数,若L满足以下条件：对L所有的边χy∈E(G),χ、y∈V(G),都有L(χ)+L(y)+L(χy)=C,C为常数,则L是图G的边幻和标号,图G是边幻和图；若在此基础上,图G的顶点标号满足：L(V(G))=｛1,2,…,l V(G)l｝,则L为图G的超边幻和标号,图G是超边幻和图；主要研究一类图的边幻和标号以及超边幻和标号,并给出了相应的证明。

超边幻和标号；超边幻和图；图

边幻和图以及超边幻和图是图论研究中一项极其有趣的内容，旨在找出某一类简单无向图的顶点标号算法和边标号的算法。图的标号问题起始于1966年A.Rosa［1］的著名的优美树猜想。超边幻和标号问题是一类图的标号问题，至今，国内外学者取得了一系列有关的重要成果［1-10］。例如Enomoto［2］等人猜想树是超边幻和图，R.M.Figueroa-Centeno［3］也研究了超边幻和图。本文给出了一类图P2n是超边幻和图的结论。

1 基本概念

定义1 对于一个给定的简单图G=（V，E），存在一个双射函数L：V（G）∪E（G）→｛1，2，…，l V（G）∪E（G）l｝，使得对所有的边χy∈E（G），χ，y∈V（G），都有L（χ）+L（y）+L（χy）=C，C为常数，则称L为图G的边幻和标号（Edge-Magic Total Labeling），图G称为具有边幻和标号L的边幻和图（Edge-Magic Total Graph）。

定义2 设L为图G（V，E）的边幻和标号，如果顶点标号满足：L（V（G））=｛1，2，…，l V（G）l｝，则称L为图G的超边幻和标号（Super Edge-Magic Total Labeling），图G称为具有超边幻和标号L的超边幻和图（Super Edge-Magic Total Graph）。

定义3 设图表示具有n个顶点且满足以下条件的图类：

（1）n∈N*，n≥3；

2 结论及其证明

定理1 对于满足定义3的一类图具有边幻和标号算法，P2n是边幻和图。

综上所述，定理1得证。

定理2 对∀n∈N*，图具有超边幻和标号算法，是超边幻和图。

证明 令超边幻和常数C=3n，定义函数L如下：

则K1∪K2∪…∪Kn是所有顶点标号的集合，且有K1∪K2∪…∪Kn=｛1，2，…，n｝。由上述可知，所有顶点标号是各不相同的，所以L是从顶点集V（P2

n）到｛1，2，…，n｝的双射函数。

其次，证明L是从E（P2n）到｛n+1，n+2，…，3n-3｝的双射函数。令

因此S1∪S2是所有边标号的集合，且有S=S1∪S2=｛n+1，n+2，…，3n-3｝。

由上述可知，每条边的标号是各不相同的，且边的标号集合为｛n+1，n+2，…，3n-3｝，所以L是从E（）到｛n+1，n+2，…，3n-3｝的双射函数。

对∀n∈N*，图的下标n一旦确定，超边幻和常数3n。根据超边幻和标号定义，可以得出结论：L为图的超边幻和标号，图是超边幻和图。

综上所述，定理2得证。

［1］KOTZIG A，ROSA A.Magic Valuations of Finite Graphs.Canad［J］.Math.Bull，1970（13）：451-461

［2］FIGUEROA CR，ICHISHIMA R，MUNTANER B F.The Place of Super Edge Magic Labelings Among other Classes of Labelings［J］.Discrete Math，2001（231）：153-168

［3］ENOMOTO H，LIADO A，NAKAMIGAWA T.Super Edge Magic Graphs［J］.SUT J.Math.，1998（34）：105-109

［4］刘家保，王林，陆一南.具有公共边的双圈图的奇优美标号及其算法［J］.合肥工业大学学报：自然科学版，2012，35（6）：857-859

［5］严谦泰.积图Pn×Pm的奇优美性和奇强协调性［J］.系统科学与数学，2010，30（3）：341-348

［6］刘家保，张季，聂东明.一类新的联图的优美标号算法［J］.汕头大学学报：自然科学版，2011（3）：8-10

［7］王涛，王清，李德明.非连通图（P3∨）∪G及（C3∨）∪G的优美性［J］.中山大学学报：自然科学版，2012，51（5）：54-57

［8］刘家保，王林，陆一南.双圈图G（n，m）的奇优美标号及其算法［J］.合肥工业大学学报：自然科学版，2012，35（5）：708-710

［9］严谦泰.P2r，2m的优美标号［J］.系统科学与数学，2006，26（5）：513-517.

［10］GALLIAN JA.A Dynamic Survey of Graph Labeling［J］.The Electronic Journal of Combinatorics，2009（16）：1-219

（1.Fundamental Courses Department，Anhui Xinhua University，Hefei230088，China；2.School of Mathematical Sciences，Anhui University，Hefei230601，China）

fffff9的边幻和标号算法及超边幻和标号算法*

刘家保1，何 芳2

The Algorithm of Edge-magic Total Labeling and Super Edge-magic Total Labeling of

LIU Jia-bao1，HE Fang2

Let L be a bijective function of simple undirected graph G from V（G）∪E（G）→｛1，2，…，l V（G）∪E（G）l｝；L was said to be a edge-magic total labeling of G and G is a edge-magic total graph if L satisfied the following：for allχy∈E（G），χ，y∈V（G）there are the results that L（χ）+L（y）+L（χy）=C，C is a constant，on the basis of it，if the vertex labeling of G satisfied L（V（G））=｛1，2，…，l V（G）l｝，then L was said to be a super edgemagic total labeling of graph G，G is a super edge-magic total graph.This paper researched the edge-magic total labeling and super edge-magic total labeling o，and gave the corresponding proofs.

super edge-magic total labeling；super edge-magic total graphs；graph

代小红

O451

A

1672-058X(2014)02-0012-04

2013-08-10;

2013-09-12.

安徽省高等学校省级自然科学基金项目（KJ2013B015）；安徽新华学院质量工程建设资助项目（2012tskcx04）

刘家保（1982-），男，安徽六安人，讲师，硕士，从事组合数学与复杂网络研究.