一類平面圖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-)，男，安徽六安人，講師，碩士，主要從事組合網絡方面的研究。

責任編輯:鐘 聲