一類平面圖I(n)的超邊幻和標(biāo)號(hào)及其算法

劉家保，王 林

(安徽新華學(xué)院 a.公共課教學(xué)部;b.計(jì)算機(jī)科學(xué)與技術(shù)系，合肥 230088)

一類平面圖I(n)的超邊幻和標(biāo)號(hào)及其算法

劉家保a，王 林b

(安徽新華學(xué)院 a.公共課教學(xué)部;b.計(jì)算機(jī)科學(xué)與技術(shù)系，合肥 230088)

探索和研究了一類新平面圖的超邊幻和標(biāo)號(hào)問題，運(yùn)用算法設(shè)計(jì)與分析中的分支限界理論和思想設(shè)計(jì)了各頂點(diǎn)和邊的超邊幻和標(biāo)號(hào)算法，給出并嚴(yán)格證明了此類新的平面圖是超邊幻和圖等結(jié)論。

超邊幻和標(biāo)號(hào);超邊幻和圖;平面圖類

0 引言

圖標(biāo)號(hào)問題是圖論中的一類重要研究課題，起始于上世紀(jì)六十年代A·Rosa的著名優(yōu)美樹猜想，其背景來源于眾多實(shí)際問題，應(yīng)用范圍廣泛深入眾多領(lǐng)域。幻類型標(biāo)號(hào)主要有邊幻和標(biāo)號(hào)、超邊幻和標(biāo)號(hào)、超點(diǎn)幻和標(biāo)號(hào)反邊幻和標(biāo)號(hào)等，是受數(shù)論中的幻方啟發(fā)提出的。超邊幻和標(biāo)號(hào)問題就是一種對(duì)圖的標(biāo)號(hào)問題，具有超邊幻和標(biāo)號(hào)的圖被稱為超邊幻和圖。Kotzig和Rosa［1］在1970年給出了邊幻和標(biāo)號(hào)的定義，Enomoto［2］等人給出了超邊幻和標(biāo)號(hào)的定義。超邊幻和標(biāo)號(hào)是其中一類條件非常嚴(yán)格的標(biāo)號(hào)，與序列標(biāo)號(hào)、調(diào)和標(biāo)號(hào)、平衡標(biāo)號(hào)和親切標(biāo)號(hào)等有著緊密的聯(lián)系，研究超邊幻和標(biāo)號(hào)問題有助于研究其它類型的圖標(biāo)號(hào)問題。

1 基本概念

定義1對(duì)于一個(gè)給定的簡(jiǎn)單圖G=(V，E)，如果G=(V，E)是有p個(gè)頂點(diǎn)q條邊的圖.假設(shè)G的頂點(diǎn)和邊由1，2，…，p+q所標(biāo)號(hào)，且 L:V∪E→{1，2，…，p+q}是一個(gè)雙射，如果對(duì)所有的邊 xy，L(x)+L(y)+L(xy)=C是個(gè)常量，則稱圖G是邊幻和圖(edge-magic total graph)，稱L為G的邊幻和標(biāo)號(hào)(edge-magic total labeling)。

定義2設(shè)L為圖G(V，E)的邊幻和標(biāo)號(hào)，如果頂點(diǎn)標(biāo)號(hào)滿足:L(V(G))={1，2，Λ，|V(G)|}，則稱L為圖G的超邊幻和標(biāo)號(hào)(super edge-magic total labeling)，圖G稱為具有超邊幻和標(biāo)號(hào)L的超邊幻和圖(super edge-magic total labeling)。

定義3對(duì)于一類平面圖I(n)，其頂點(diǎn)集和邊集分別為V(I(n))和E(I(n))，如果圖I(n)是具有n+4個(gè)頂點(diǎn)和2n+5條邊的圖，各頂點(diǎn)和邊均由集合A={1，2，…，3n+9}中的元素所標(biāo)號(hào)，且存在一個(gè)雙射函數(shù)L:V(I(n))∪E(I(n))→{1，2，…，3n+9}，則圖I(n)是表示滿足以下條件的圖類:

(1)頂點(diǎn)集為 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 主要結(jié)果

設(shè)平面圖I(n)=(V，E)，其頂點(diǎn)集和邊集分別為V(I(n))和E(I(n))，則頂點(diǎn)數(shù)|V(I(n))|=n+4，邊數(shù)|E(I(n))|=2n+5。

由于圖I(n)存在一個(gè)雙射函數(shù)L:V(I(n))→{1，2，…，n+4}使得k={L(x)+L(y):xy∈E(I(n))}中的元素均為連續(xù)整數(shù)。在此條件下，L可擴(kuò)展為圖I(n)的超邊幻和標(biāo)號(hào)，其中常數(shù)C=|V(I(n))|+|E(I(n))|+m，m=min(k)，并且 k={C －(n+5)，C －(n+6)，…，C －(3n+9)}。若 L為圖 I(n)的標(biāo)號(hào)，?xy∈E(I(n))，則邊幻常數(shù)C為:L(x)+L(xy)+L(y)=3n+12。

定義函數(shù)L:V(I(n))∪E(I(n))→{1，2，…，3n+9}，我們給出圖I(n)各頂點(diǎn)和邊的標(biāo)號(hào)算法如下:

(Ⅰ)圖I(n)各頂點(diǎn)標(biāo)號(hào)的算法A為:

(Ⅱ)圖I(n)各邊標(biāo)號(hào)的算法B為:

定理1對(duì)?n∈N*，一類新的平面圖I(n)是超邊幻和圖。

證明運(yùn)用算法設(shè)計(jì)與分析的分支限界策略進(jìn)行嚴(yán)格的數(shù)學(xué)證明。

首先，證明L是從頂點(diǎn)集V(I(n))到{1，2，…，n+4}的雙射函數(shù)。

令 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是所有頂點(diǎn)標(biāo)號(hào)的集合，且有:

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

由上述可知，所有頂點(diǎn)的標(biāo)號(hào)是各不相同的，所以L是一個(gè)從V(I(n))到{1，2，…，n+4}的雙射函數(shù)。

其次，證明L是從E(I(n))到{n+5，n+6，…，3n+9}的雙射函數(shù)。

令 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是所有邊的標(biāo)號(hào)的集合，且有:

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}

由上述可知，每條邊的標(biāo)號(hào)是各不相同的，且邊的標(biāo)號(hào)的集合為:{n+5，n+6，…，3n+9}，所以L是一個(gè)從 V(I(n))到{1，2，…，3n+9}的雙射函數(shù)。

根據(jù)超邊幻和標(biāo)號(hào)的定義，對(duì)?n∈N*，且圖I(n)的n確定，邊幻和常數(shù)C=3n+12，可以得出結(jié)論:圖I(n)是超邊幻和圖。綜上所述，定理1得證。

3 結(jié)語(yǔ)

圖論的超邊幻和標(biāo)號(hào)是圖標(biāo)號(hào)問題中的一類條件非常嚴(yán)格的標(biāo)號(hào)，由于此類標(biāo)號(hào)與序列標(biāo)號(hào)、調(diào)和標(biāo)號(hào)、平衡標(biāo)號(hào)和親切標(biāo)號(hào)等其它類型的標(biāo)號(hào)有著廣泛的聯(lián)系，研究和解決超邊幻和標(biāo)號(hào)問題有助于研究其它圖類的標(biāo)號(hào)問題。借助計(jì)算機(jī)工具，運(yùn)用算法設(shè)計(jì)和分析，有助于超邊幻和標(biāo)號(hào)算法的探索和超邊幻和圖結(jié)論的證明。

本文運(yùn)用算法設(shè)計(jì)與分析中的分支界限策略設(shè)計(jì)和給出了一類新的平面圖I(n)的超邊幻和標(biāo)號(hào)算法，得出了I(n)的各頂點(diǎn)和邊的超邊幻和標(biāo)號(hào)，并對(duì)其是超邊幻和圖給出了嚴(yán)格的數(shù)學(xué)證明。對(duì)于其它的平面圖類是否具有超邊幻和標(biāo)號(hào)算法和超邊幻和圖等結(jié)論，有待進(jì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－冠的新的優(yōu)美標(biāo)號(hào)［J］.純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2010，26(3):454－457.

［5］ 陳淑貞，周俊梅.關(guān)于聯(lián)圖P1∨Pn的K－強(qiáng)優(yōu)美性［J］.數(shù)學(xué)雜志，2010，30(2):357－362.

［6］ 劉家保，潘向峰.輪形圖和扇形圖的優(yōu)美性［J］.安徽大學(xué)學(xué)報(bào):自然科學(xué)版，2009，133(4):11－13.

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

［8］ 魏麗俠，張昆龍.圖K1∨Cn的非連通并圖的優(yōu)美性［J］.中山大學(xué)學(xué)報(bào):自然科學(xué)版，2007，46(4):13－16.

［9］ 容青，熊冬春.P2r，b圖優(yōu)美性［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2010，30(5):203－209.

［10］ 劉家保，張季，聶東明.一類新的聯(lián)圖的優(yōu)美標(biāo)號(hào)算法［J］.汕頭大學(xué)學(xué)報(bào):自然科學(xué)版，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

安徽省高等學(xué)校省級(jí)自然科學(xué)基金項(xiàng)目(KJ2010B076)

劉家保(1982-)，男，安徽六安人，講師，碩士，主要從事組合網(wǎng)絡(luò)方面的研究。

責(zé)任編輯:鐘 聲