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

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

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

本文主要研究利用算法得到有限點(diǎn)內(nèi)所有圖的邊幻和全標(biāo)號(hào)，然后從結(jié)果集中分析所有雙圈圖與星圖組合聯(lián)圖的標(biāo)號(hào)規(guī)律，總結(jié)為若干定理并給出證明.

1 基礎(chǔ)知識(shí)

本文所研究的圖均為無向簡(jiǎn)單連通圖，對(duì)于圖G(p，q)，當(dāng)q=p+1時(shí)，稱G為雙圈圖.文中的星圖Sm定義為有m-1個(gè)葉子節(jié)點(diǎn)和1個(gè)中心節(jié)點(diǎn)v1.

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

定義2將圈圖Cn和Cl任意一頂點(diǎn)并接，設(shè)并接點(diǎn)為u1/w1，再將并接點(diǎn)u1/w1和星Sm中心節(jié)點(diǎn)v1鄰接得到的聯(lián)圖，記為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任意一頂點(diǎn)并接，設(shè)并接點(diǎn)為u1/w1，再將并接點(diǎn)u1/w1和星Sm中心節(jié)點(diǎn)v1并接得到的聯(lián)圖，記為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對(duì)于雙圈圖G(p，q)，設(shè)圖中任意相鄰頂點(diǎn)u，v及其邊w的標(biāo)號(hào)組成三元組(u，v，w)，存在正整數(shù)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的相鄰點(diǎn)u，v和邊標(biāo)號(hào)w的三元組(u，v，w).

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

2 EMTL算法

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

(1)

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

得公式

(2)

由于公式(2)中只涉及到點(diǎn)的標(biāo)號(hào)，無法遍歷所有解空間，將所有邊的標(biāo)號(hào)系數(shù)設(shè)為0，并進(jìn)行求和，得到公式

(3)

令

則有

q*k=C+S.

(4)

EMTL算法思想：

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

2)初始化f(vi)，按度序列由大到小的順序進(jìn)行標(biāo)號(hào).

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

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

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

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

EMTL算法描述：

輸入：鄰接矩陣

輸出：標(biāo)號(hào)矩陣

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對(duì)于雙圈圖G(p，q)，當(dāng)4≤p≤15，均為EMTL圖.

證明1) 對(duì)于雙圈圖G(p，q)，當(dāng)4≤p≤15時(shí)，根據(jù)公式(4)可得邊幻和常數(shù)12≤k≤62，對(duì)應(yīng)的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算法，得到結(jié)果如表3所示.

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

3)圖2為G(15，16)成功標(biāo)號(hào)示例.

定理2對(duì)于聯(lián)圖CnΔClSm，n=l，當(dāng)3≤n≤5，m≥1時(shí)，具有EMTL.

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

1) 當(dāng)n=3時(shí)，如圖3所示.

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

由公式(4)計(jì)算，邊幻和常數(shù)K∈[2m+14，4m+22].當(dāng)K=2m+14時(shí)，頂點(diǎn)標(biāo)號(hào)為：

(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

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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) 當(dāng)n=4時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+18，4m+30].當(dāng)K=2m+19時(shí)，

i) 當(dāng)m=1時(shí)，C4ΔC4S1的EMTL如圖4(a)；

ii) 當(dāng)m≥2時(shí)，頂點(diǎn)標(biāo)號(hào)如下：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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) 當(dāng)n=5時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+22，4m+38].當(dāng)K=2m+24時(shí)，

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

ii) 當(dāng)m≥3時(shí)，頂點(diǎn)標(biāo)號(hào)如下：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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對(duì)于聯(lián)圖CnΔClΔSm，當(dāng)3≤n≤5，3≤l≤6，m≥2，具有EMTL.

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

1) 當(dāng)n=3，l=3時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+12，4m+18].當(dāng)K=2m+12時(shí)，頂點(diǎn)標(biāo)號(hào)為：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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) 當(dāng)n=3，l=4時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+14，4m+22].當(dāng)K=2m+14時(shí)，

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

ii) 當(dāng)m≥3時(shí)，頂點(diǎn)標(biāo)號(hào)如下：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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) 當(dāng)n=3，l=5時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+16，4m+26].當(dāng)K=2m+16時(shí)，

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

ii) 當(dāng)m≥5時(shí)，頂點(diǎn)標(biāo)號(hào)如下：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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) 當(dāng)n=3，l=6時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+18，4m+30].當(dāng)K=2m+19時(shí)，

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

ii) 當(dāng)m≥3時(shí)，頂點(diǎn)標(biāo)號(hào)如下：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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) 當(dāng)n=4，l=4時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+16，4m+26].當(dāng)K=2m+17時(shí)，頂點(diǎn)標(biāo)號(hào)為：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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) 當(dāng)n=4，l=5時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+18，4m+30].當(dāng)K=2m+19時(shí)，

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

ii) 當(dāng)m≥3時(shí)，頂點(diǎn)標(biāo)號(hào)如下：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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) 當(dāng)n=5，l=5時(shí)，如圖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)計(jì)算，邊幻和常數(shù)K∈[2m+20，4m+34].當(dāng)K=2m+22時(shí)，

i) 當(dāng)m=2時(shí)，C5ΔC5ΔS2的EMTL如圖12(a)；

ii) 當(dāng)m≥3時(shí)，頂點(diǎn)標(biāo)號(hào)如下：

圖中相鄰兩點(diǎn)之和集合A、頂點(diǎn)標(biāo)號(hào)集合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}，

計(jì)算得邊標(biāo)號(hào)集合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.

猜測(cè)1對(duì)于雙圈圖CnΔClSm和CnΔClΔSm，當(dāng)n≥6，l≥7，m≥1時(shí)，均有EMTL.

猜測(cè)2雙圈圖均為EMTL圖.

4 結(jié)論

本文利用EMTL算法，得到了15個(gè)點(diǎn)內(nèi)的所有雙圈圖的邊幻和標(biāo)號(hào)，從結(jié)果中分析找出兩類聯(lián)圖CnΔClSm與CnΔClΔSm的標(biāo)號(hào)規(guī)律，總結(jié)歸納了3條定理并給出證明，進(jìn)而猜測(cè)：所有雙圈圖均有EMTL.