（1.安徽新華學(xué)院公共課程部，合肥 230088；2.安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，合肥 230601）

（1.安徽新華學(xué)院公共課程部，合肥 230088；2.安徽大學(xué)數(shù)學(xué)科學(xué)學(xué)院，合肥 230601）

設(shè)L為簡單無向圖G從V(G)∪E(G)→｛1,2,…,l V(G)∪E(G)l｝的一個(gè)雙射函數(shù),若L滿足以下條件：對(duì)L所有的邊χy∈E(G),χ、y∈V(G),都有L(χ)+L(y)+L(χy)=C,C為常數(shù),則L是圖G的邊幻和標(biāo)號(hào),圖G是邊幻和圖；若在此基礎(chǔ)上,圖G的頂點(diǎn)標(biāo)號(hào)滿足：L(V(G))=｛1,2,…,l V(G)l｝,則L為圖G的超邊幻和標(biāo)號(hào),圖G是超邊幻和圖；主要研究一類圖的邊幻和標(biāo)號(hào)以及超邊幻和標(biāo)號(hào),并給出了相應(yīng)的證明。

超邊幻和標(biāo)號(hào)；超邊幻和圖；圖

邊幻和圖以及超邊幻和圖是圖論研究中一項(xiàng)極其有趣的內(nèi)容，旨在找出某一類簡單無向圖的頂點(diǎn)標(biāo)號(hào)算法和邊標(biāo)號(hào)的算法。圖的標(biāo)號(hào)問題起始于1966年A.Rosa［1］的著名的優(yōu)美樹猜想。超邊幻和標(biāo)號(hào)問題是一類圖的標(biāo)號(hào)問題，至今，國內(nèi)外學(xué)者取得了一系列有關(guān)的重要成果［1-10］。例如Enomoto［2］等人猜想樹是超邊幻和圖，R.M.Figueroa-Centeno［3］也研究了超邊幻和圖。本文給出了一類圖P2n是超邊幻和圖的結(jié)論。

1 基本概念

定義1 對(duì)于一個(gè)給定的簡單圖G=（V，E），存在一個(gè)雙射函數(shù)L：V（G）∪E（G）→｛1，2，…，l V（G）∪E（G）l｝，使得對(duì)所有的邊χy∈E（G），χ，y∈V（G），都有L（χ）+L（y）+L（χy）=C，C為常數(shù)，則稱L為圖G的邊幻和標(biāo)號(hào)（Edge-Magic Total Labeling），圖G稱為具有邊幻和標(biāo)號(hào)L的邊幻和圖（Edge-Magic Total Graph）。

定義2 設(shè)L為圖G（V，E）的邊幻和標(biāo)號(hào)，如果頂點(diǎn)標(biāo)號(hào)滿足：L（V（G））=｛1，2，…，l V（G）l｝，則稱L為圖G的超邊幻和標(biāo)號(hào)（Super Edge-Magic Total Labeling），圖G稱為具有超邊幻和標(biāo)號(hào)L的超邊幻和圖（Super Edge-Magic Total Graph）。

定義3 設(shè)圖表示具有n個(gè)頂點(diǎn)且滿足以下條件的圖類：

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

2 結(jié)論及其證明

定理1 對(duì)于滿足定義3的一類圖具有邊幻和標(biāo)號(hào)算法，P2n是邊幻和圖。

綜上所述，定理1得證。

定理2 對(duì)?n∈N*，圖具有超邊幻和標(biāo)號(hào)算法，是超邊幻和圖。

證明 令超邊幻和常數(shù)C=3n，定義函數(shù)L如下：

則K1∪K2∪…∪Kn是所有頂點(diǎn)標(biāo)號(hào)的集合，且有K1∪K2∪…∪Kn=｛1，2，…，n｝。由上述可知，所有頂點(diǎn)標(biāo)號(hào)是各不相同的，所以L是從頂點(diǎn)集V（P2

n）到｛1，2，…，n｝的雙射函數(shù)。

其次，證明L是從E（P2n）到｛n+1，n+2，…，3n-3｝的雙射函數(shù)。令

因此S1∪S2是所有邊標(biāo)號(hào)的集合，且有S=S1∪S2=｛n+1，n+2，…，3n-3｝。

由上述可知，每條邊的標(biāo)號(hào)是各不相同的，且邊的標(biāo)號(hào)集合為｛n+1，n+2，…，3n-3｝，所以L是從E（）到｛n+1，n+2，…，3n-3｝的雙射函數(shù)。

對(duì)?n∈N*，圖的下標(biāo)n一旦確定，超邊幻和常數(shù)3n。根據(jù)超邊幻和標(biāo)號(hào)定義，可以得出結(jié)論：L為圖的超邊幻和標(biāo)號(hào)，圖是超邊幻和圖。

綜上所述，定理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］劉家保，王林，陸一南.具有公共邊的雙圈圖的奇優(yōu)美標(biāo)號(hào)及其算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，35（6）：857-859

［5］嚴(yán)謙泰.積圖Pn×Pm的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2010，30（3）：341-348

［6］劉家保，張季，聶東明.一類新的聯(lián)圖的優(yōu)美標(biāo)號(hào)算法［J］.汕頭大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（3）：8-10

［7］王濤，王清，李德明.非連通圖（P3∨）∪G及（C3∨）∪G的優(yōu)美性［J］.中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，51（5）：54-57

［8］劉家保，王林，陸一南.雙圈圖G（n，m）的奇優(yōu)美標(biāo)號(hào)及其算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，35（5）：708-710

［9］嚴(yán)謙泰.P2r，2m的優(yōu)美標(biāo)號(hào)［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，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的邊幻和標(biāo)號(hào)算法及超邊幻和標(biāo)號(hào)算法*

劉家保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.

安徽省高等學(xué)校省級(jí)自然科學(xué)基金項(xiàng)目（KJ2013B015）；安徽新華學(xué)院質(zhì)量工程建設(shè)資助項(xiàng)目（2012tskcx04）

劉家保（1982-），男，安徽六安人，講師，碩士，從事組合數(shù)學(xué)與復(fù)雜網(wǎng)絡(luò)研究.