雙圈圖邊幻和全標號

邵淑宏，李敬文，顧彥波，王筆美

(蘭州交通大學電子與信息工程學院，蘭州 730070)

圖論以圖為研究對象，在圖中用點表示對象，兩點之間的連線表示對象之間的某種特定的關系.圖論在自然科學、社會科學等各領域都有廣泛的應用.圖的標號問題是圖論的研究方向之一.Kotzig和Rosa[1]在1970年首次提出了圖的邊幻和全標號的概念.目前，國內外關于圖優美標號的結果已有很多[2-5]，這些結果為圖的邊幻和標號的后續發展奠定了基礎.1998年Enomoto[6]證明了當n為奇數時，所有的Cn均為超邊幻和圖，當m=1或n=1時，Km ，n為超邊幻和圖，當n≠3(mod4)時，Wn為邊幻和圖；Tn、Pn、sun、Kn、Km ，n、Cm×Cn均為邊幻和圖[7-8]；文獻[9-11]證明了當n≥3時所有的Cn均為邊幻和圖；Lin[12]等人在2002年給出了部分Fn、友誼圖的邊幻和標號；Wijaya[13]證明了n為奇數且n≥3時，Pm×Cn為邊幻和圖；文獻[14]證明了當m，n滿足一定條件時，Cm∪Cn圖為超邊幻和圖.針對特殊圖的邊幻和性，Gallian[15]總結歸納了現有的所有標號種類及研究結果，并給出了相應的證明.

本文主要研究利用算法得到有限點內所有圖的邊幻和全標號，然后從結果集中分析所有雙圈圖與星圖組合聯圖的標號規律，總結為若干定理并給出證明.

1 基礎知識

本文所研究的圖均為無向簡單連通圖，對于圖G(p，q)，當q=p+1時，稱G為雙圈圖.文中的星圖Sm定義為有m-1個葉子節點和1個中心節點v1.

定義1[6-7]設f為簡單無向圖G(p，q)從V(G)∪E(G)→{1，2，…，p+q}的一個雙射函數.若f滿足以下條件：對于圖G所有的邊uv∈E(G)，點uv∈V(G)，都有f(u)+f(v)+f(uv)=k，k為邊幻和常數，則f是圖G的邊幻和標號(edge-magic total labelling)，簡稱EMTL，圖G是邊幻和圖(edge-magic graph).若圖G的頂點標號滿足：f(V(G))→{1，2，…，p}，則f是圖G的超級邊幻和標號(super edge-magic total labelling)，簡稱SEMTL，圖G是超級邊幻和圖(super edge-magic graph).

定義2將圈圖Cn和Cl任意一頂點并接，設并接點為u1/w1，再將并接點u1/w1和星Sm中心節點v1鄰接得到的聯圖，記為CnΔClSm，V(CnΔClSm)=V(Cn)∪V(Cl)∪V(Sm)v，即|V(CnΔClSm)|=|V(Cn)|+|V(Cl)|+|V(Sm)|-1，E(CnΔClSm)=E(Cn)∪E(Cl)∪E(Sm)∪(u1/w1)v1，即|E(CnΔClSm)|=|E(Cn)|+|E(Cl)|+|E(Sm)|+1.

示例如圖1(a).

定義3將圈圖Cn和Cl任意一頂點并接，設并接點為u1/w1，再將并接點u1/w1和星Sm中心節點v1并接得到的聯圖，記為CnΔClΔSm，V(CnΔClΔSm)=V(Cn)∪V(Cl)∪V(Sm)2v，即|V(CnΔClΔSm)|=|V(Cn)|+|V(Cl)|+|V(Sm)|-2，E(CnΔClΔSm)=E(Cn)∪E(Cl)∪E(Sm).

示例如圖1(b).

定義4對于雙圈圖G(p，q)，設圖中任意相鄰頂點u，v及其邊w的標號組成三元組(u，v，w)，存在正整數k(k的取值范圍為：p+q+3≤k≤2(p+q))，使得u+v+w=k成立，其中u，v，w∈[1，p+q]，并且u，v，w取值各不相同，則稱三元組(u，v，w)的取值空間為雙圈圖G(p，q)的EMTL解空間，記為δ(p，q，k).如表1所示.

(a)C3ΔC3S3 (b)C3ΔC3ΔS3圖1 C3ΔC3S3和C3ΔC3ΔS3Fig.1 C3ΔC3S3and C3ΔC3ΔS3

表1 k-EMTL解空間δ(p，q，k)Tab.1 The solution space δ(p，q，k) for k-EMTL

由定義1和定義2，以下引理顯然成立．

引理1如果(p，q)圖存在EMTL，則解空間δ(p，q，k)中一定存在滿足EMTL的相鄰點u，v和邊標號w的三元組(u，v，w).

引理2如果(p，q)圖為非EMTL，則解空間δ(p，q，k)中一定不存在正整數k(k的取值范圍為p+q+3≤k≤2(p+q))和q組(u，v，w)，使得相鄰點u，v和邊標號w的三元組(u，v，w)滿足u+v+w=k，其中u，v，w∈[1，p+q]，并且u，v，w取值各不相同.

2 EMTL算法

根據EMTL定義，f(u)+f(v)+f(uv)=k，求和得公式

(1)

其中deg(vi)表示頂點vi的度，令vdc(vi)=deg(vi)-1，常數

得公式

(2)

由于公式(2)中只涉及到點的標號，無法遍歷所有解空間，將所有邊的標號系數設為0，并進行求和，得到公式

(3)

令

則有

q*k=C+S.

(4)

EMTL算法思想：

1)根據以上公式計算圖G的度序列系數vdc(vi)、C、S的值，并將vdc(vi)、C、S的值代入到公式(4)，計算k的取值.

2)初始化f(vi)，按度序列由大到小的順序進行標號.

(i)判斷k的取值范圍是否滿足p+q+3≤k≤2(p+q)，若存在正整數k使得等式成立，則進入分配函數Labelling，否則，則對vdc(vi)與0組合做一次全排列.

(ii)若分配成功，則表示該圖有EMTL，退出循環，算法結束；否則，則對vdc(vi)與0組合做一次全排列.循環執行此操作.

(iii)直到分配成功或者所有的全排列做完，則算法結束.

3)若全排列做完后該圖還未標成功，則表示該圖為非EMTL圖.

EMTL算法描述：

輸入：鄰接矩陣

輸出：標號矩陣

1 Calculatevdc(vi)、C;

2 is Conflict=true;

3 do

4 CalculateS;

5 if (C+S)%q==0

6 Calculatek;

7 if(Labelling(vdc(vi)，k))

8 is Conflict=false;

9 is Success=true;

10 return;

11 end if

12 end if

13 Find the rightvdc(vi)

14 while(is Conflict)

3 定理及證明

定理1對于雙圈圖G(p，q)，當4≤p≤15，均為EMTL圖.

證明1) 對于雙圈圖G(p，q)，當4≤p≤15時，根據公式(4)可得邊幻和常數12≤k≤62，對應的k-EMTL空間如表2所示.

表2 (p，p+1)圖的k-EMTL空間 (p≤15)Tab.2 k-EMTL space for G(p，q) when p≤15

2) 利用EMTL算法，得到結果如表3所示.

表3 (p，p+1)圖的EMTL (p≤15)Tab.3 EMTL for G(p，p+1) when p≤15

3)圖2為G(15，16)成功標號示例.

定理2對于聯圖CnΔClSm，n=l，當3≤n≤5，m≥1時，具有EMTL.

證明設CnΔClSm的頂點集合分別為{u1，u2，…，un}、{w1，w2，…，wl}、{v1，v2，…，vm}.

1) 當n=3時，如圖3所示.

|V(G)|=3+3+m-1=m+5，|E(G)|=3+3+(m-1)+1=m+6.

由公式(4)計算，邊幻和常數K∈[2m+14，4m+22].當K=2m+14時，頂點標號為：

(a) G(15，16) (b) G(15，16)圖2 圖G(p，p+1)的EMTL示例圖Fig.2 Examples for EMTL of G(p，p+1)

圖3 C3ΔC3 SmFig.3 C3ΔC3 Sm

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={4，3，8，7}∪

{5，6，9}∪{10，11，…，m+8}，

f(V)={1，2，6}∪

{4，5}∪{3}∪{7，8，…，m+5}，

計算得邊標號集合f(E)為

f(E)={2m+10，2m+11，2m+6，2m+7}∪

{2m+9，2m+8，2m+5}∪

{2m+4，2m+3，…，m+6}，

由于f(V)∪f(E)→[1，2m+11]，且f(V)∩f(E)=?，故C3ΔC3Sm具有EMTL.

2) 當n=4時，如圖4所示.

(a) C4ΔC4S1 (b) C4ΔC4Sm (m≥2)圖4 C4ΔC4SmFig.4 C4ΔC4Sm

|V(G)|=4+4+m-1=m+7，

|E(G)|=4+4+(m-1)+1=m+8．

由公式(4)計算，邊幻和常數K∈[2m+18，4m+30].當K=2m+19時，

i) 當m=1時，C4ΔC4S1的EMTL如圖4(a)；

ii) 當m≥2時，頂點標號如下：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={5，6，7，10，11}∪{4，8，9，13}∪

{12}∪{14，15，…，m+11}，

f(V)={1，2，5，9}∪{3，6，7}∪

{4}∪{8}∪{10，11，…，m+7}，

計算得邊標號集合f(E)為

f(E)=

{2m+14，2m+13，2m+12，2m+8，2m+9}∪

{2m+15，2m+11，2m+10，2m+6}∪

{2m+7}∪{2m+5，2m+4，…，m+8}，

由于f(V)∪f(E)→[1，2m+15]，且f(V)∩f(E)=?，故C4ΔC4Sm具有EMTL.

3) 當n=5時，如圖5所示.

(a) C5ΔC5S1 (b)C5ΔC5S2 (c) C5ΔC5Sm(m≥3) 圖5 C5ΔC5SmFig.5 C5ΔC5Sm

|V(G)|=5+5+m-1=m+9，

|E(G)|=5+5+(m-1)+1=m+10，

由公式(4)計算，邊幻和常數K∈[2m+22，4m+38].當K=2m+24時，

i) 當m=1，2時，C5ΔC5S1、C5ΔC5S2的EMTL如圖5(a)；

ii) 當m≥3時，頂點標號如下：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={6，5，7，9，13，14}∪

{8，10，11，12，17}∪{15，16}∪

{18，19，…，m+14}，

f(V)={1，2，3，6，12}∪{4，7，8，9}∪

{5}∪{10，11}∪{13，14，…，m+9}，

計算得邊標號集合f(E)為：

f(E)={2m+18，2m+19，2m+17，2m+15，

2m+11，2m+10}∪{2m+16，2m+14，

2m+13，2m+12，2m+7}∪{2m+9，2m+8}∪

{2m+6，2m+5，…，m+10}，

由于f(V)∪f(E)→[1，2m+19]，且f(V)∩f(E)=?，故C5ΔC5Sm具有EMTL.

定理3對于聯圖CnΔClΔSm，當3≤n≤5，3≤l≤6，m≥2，具有EMTL.

證明設CnΔClΔSm的頂點集合分別為{u1，u2，…，un}、{w1，w2，…，wl}、{v1，v2，…，vm}.

1) 當n=3，l=3時，如圖6所示.

圖6 C3ΔC3ΔSmFig.6 C3ΔC3ΔSm

|V(G)|=3+3+m-2=m+4，|E(G)|=3+3+(m-1)=m+5，

由公式(4)計算，邊幻和常數K∈[2m+12，4m+18].當K=2m+12時，頂點標號為：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={3，m+5，m+6}∪

{5，m+4，m+7}∪{4}∪{6，…，m+3}，

f(V)={1，2，m+4}∪{4，m+3}∪

{3}∪{5，6，…，m+2}，

計算得邊標號集合f(E)為

f(E)={2m+9，m+7，m+6}∪

{2m+7，m+8，m+5}∪

{2m+8}∪{2m+6，2m+5，…，m+9}，

由于f(V)∪f(E)→[1，2m+9]，且f(V)∩f(E)=?，故C3ΔC3ΔSm具有EMTL.

2) 當n=3，l=4時，如圖7所示.

(a) C3ΔC4ΔS2 (b) C3ΔC4ΔSm (m≥3)圖7 C3ΔC4ΔSmFig.7 C3ΔC4ΔSm

|V(G)|=3+4+m-2=m+5，|E(G)|=3+4+(m-1)=m+6，

由公式(4)計算，邊幻和常數K∈[2m+14，4m+22].當K=2m+14時，

i) 當m=2時，C3ΔC4ΔS2的EMTL如圖7(a)；

ii) 當m≥3時，頂點標號如下：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={5，m+3，m+6}∪

{3，m+7，m+8，4}∪{6，7，…，m+2}∪

{m+4，m+5}，

f(V)={1，4，m+2}∪{2，m+5，3}∪

{5，6，m+1}∪{m+3，m+4}，

計算得邊標號集合f(E)為

f(E)={2m+9，m+11，m+8}∪

{2m+11，m+7，m+6，2m+10}∪

{2m+8，2m+7，…，m+12}∪

{m+10，m+9}，

由于f(V)∪f(E)→[1，2m+11]，且f(V)∩f(E)=?，故C3ΔC4ΔSm具有EMTL.

3) 當n=3，l=5時，如圖8所示.

(a) C3ΔC5ΔS2 (b)C3ΔC5ΔS3 (c)C3ΔC5ΔS4 (d) C3ΔC5ΔSm (m≥5) 圖8 C3ΔC5ΔSmFig.8 C3ΔC5ΔSm

|V(G)|=3+5+m-2=m+6，

|E(G)|=3+5+(m-1)=m+7，

由公式(4)計算，邊幻和常數K∈[2m+16，4m+26].當K=2m+16時，

i) 當m=2，3，4時，C3ΔC5ΔS2、C3ΔC5ΔS3和C3ΔC5ΔS4的EMTL如圖8(a)；

ii) 當m≥5時，頂點標號如下：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={3，5，4}∪

{6，m+9，m+8，m+5，m+2}∪

{8，9，…，m+4}∪{m+6，m+7}，

f(V)={1，2，3}∪{5，m+4，4，m+1}∪

{7，8，…，m+3}∪{m+5，m+6}，

計算得邊標號集合f(E)為

f(E)={2m+13，2m+11，2m+12}∪

{2m+10，m+7，m+8，m+11，m+14}∪

{2m+9，2m+8，…，m+12}∪

{m+10，m+9}，

由于f(V)∪f(E)→[1，2m+13]，且f(V)∩f(E)=?，故C3ΔC5ΔSm具有EMTL.

4) 當n=3，l=6時，如圖9所示.

(a) C3ΔC6ΔS2 (b) C3ΔC6ΔSm (m≥3)圖9 C3ΔC6ΔSmFig.9 C3ΔC6ΔSm

|V(G)|=3+6+m-2=m+7，|E(G)|=3+6+(m-1)=m+8，

由公式(4)計算，邊幻和常數K∈[2m+18，4m+30].當K=2m+19時，

i) 當m=2時，C3ΔC6ΔS2的EMTL如圖9(a)；

ii) 當m≥3時，頂點標號如下：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={5，m+4，m+7}∪

{4，m+10，m+9，m+8，m+11，6}∪

{7，8，…，m+3}∪{m+5，m+6}，

f(V)={1，4，m+3}∪

{3，m+7，2，m+6，5}∪

{6，7，…，m+2}∪{m+4，m+5}，

計算得邊標號集合f(E)為

f(E)={2m+14，m+15，m+12}∪

{2m+15，m+9，m+10，m+11，m+8，2m+13}∪

{2m+12，2m+11，…，m+16}∪

{m+14，m+13}，

由于f(V)∪f(E)→[1，2m+15]，且f(V)∩f(E)=?，故C3ΔC6ΔSm具有EMTL.

5) 當n=4，l=4時，如圖10所示.

圖10 C4ΔC4ΔSmFig.10 C4ΔC4ΔSm

|V(G)|=4+4+m-2=m+6，|E(G)|=4+4+(m-1)=m+7，

由公式(4)計算，邊幻和常數K∈[2m+16，4m+26].當K=2m+17時，頂點標號為：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={5，6，m+8，m+7}∪

{m+5，m+9，m+10，m+6}∪

{4}∪{7，8，…，m+4}，

f(V)={1，4，2，m+6}∪

{m+4，5，m+5}∪{3}∪{6，7，…，m+3}，

計算得邊標號集合f(E)為

f(E)={2m+12，2m+11，m+9，m+10}∪ {m+12，m+8，m+7，m+11}∪ {2m+13}∪{2m+10，2m+9，…，m+13}，

由于f(V)∪f(E)→[1，2m+13]，且f(V)∩f(E)=?，故C4ΔC4ΔSm具有EMTL.

6) 當n=4，l=5時，如圖11所示.

(a) C4ΔC5ΔS2 (b) C4ΔC5ΔSm (m≥3)圖11 C4ΔC5ΔSmFig.11 C4ΔC5ΔSm

|V(G)|=4+5+m-2=m+7，|E(G)|=4+5+(m-1)=m+8，

由公式(4)計算，邊幻和常數K∈[2m+18，4m+30].當K=2m+19時，

i) 當m=2時，C4ΔC5ΔS2的EMTL如圖11(a)；

ii) 當m≥3時，頂點標號如下：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={4，5，m+9，m+8}∪

{6，m+11，m+10，m+7，m+4}∪

{7，8，…，m+3}∪{m+5，m+6}，

f(V)={1，3，2，m+7}∪

{5，m+6，4，m+3}∪

{6，7，…，m+2}∪{m+4，m+5}，

計算得邊標號集合f(E)為

f(E)={2m+15，2m+14，m+10，m+11}∪ {2m+13，m+8，m+9，m+12，m+15}∪ {2m+12，2m+11，…，m+16}∪ {m+14，m+13}，

由于f(V)∪f(E)→[1，2m+15]，且f(V)∩f(E)=?，故C4ΔC5ΔSm具有EMTL.

7) 當n=5，l=5時，如圖12所示.

(a) C5ΔC5ΔS2 (b) C5ΔC5ΔSm (m≥3)圖12 C5ΔC5ΔSmFig.12 C5ΔC5ΔSm

|V(G)|=5+5+m-2=m+8，|E(G)|=5+5+(m-1)=m+9，

由公式(4)計算，邊幻和常數K∈[2m+20，4m+34].當K=2m+22時，

i) 當m=2時，C5ΔC5ΔS2的EMTL如圖12(a)；

ii) 當m≥3時，頂點標號如下：

圖中相鄰兩點之和集合A、頂點標號集合f(V)分別為：

A={m+6，m+7，m+8，m+13，8}∪

{6，m+12，m+10，m+11，m+9}∪

{5，7}∪{9，10，…，m+5}，

f(V)={1，m+5，2m+6，7}∪

{5，m+7，3，m+8}∪{4，6}∪{8，9，…，m+4}，

計算得邊標號集合f(E)為

f(E)={m+16，m+15，m+14，m+9，2m+14}∪

{2m+16，m+10，m+12，m+11，m+13}∪

{2m+17，2m+15}∪

{2m+13，2m+12，…，2m+17}，

由于f(V)∪f(E)→[1，2m+17]，且f(V)∩f(E)=?，故C5ΔC5ΔSm具有EMTL.

猜測1對于雙圈圖CnΔClSm和CnΔClΔSm，當n≥6，l≥7，m≥1時，均有EMTL.

猜測2雙圈圖均為EMTL圖.

4 結論

本文利用EMTL算法，得到了15個點內的所有雙圈圖的邊幻和標號，從結果中分析找出兩類聯圖CnΔClSm與CnΔClΔSm的標號規律，總結歸納了3條定理并給出證明，進而猜測：所有雙圈圖均有EMTL.