圖(p≤9)的邊幻和全標(biāo)號(hào)

顧 彥 波， 李 敬 文， 火 金 萍， 邵 淑 宏

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

0 引 言

圖論廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、復(fù)雜網(wǎng)絡(luò)及化學(xué)等領(lǐng)域，而圖的標(biāo)號(hào)問題是圖論中的熱門研究之一．1970年Anton等首次提出了圖的邊幻和全標(biāo)號(hào)概念，并研究了一些特殊圖的邊幻和全標(biāo)號(hào)[1]．目前，國(guó)內(nèi)外學(xué)者對(duì)于邊幻和全標(biāo)號(hào)的研究只是針對(duì)于一些特殊圖，如樹圖、圈圖及其相關(guān)圖、并圖和一些非連通圖[2-5]．1970年Anton等提出了猜想：所有的樹圖都有邊幻和全標(biāo)號(hào)[1]；1998年Enomoto等進(jìn)一步提出：所有的樹圖都有超級(jí)邊幻和全標(biāo)號(hào)[6]；Fukuchi證明了當(dāng)n(mod 4)?3時(shí)，Wn均具有邊幻和全標(biāo)號(hào)[7]；文獻(xiàn)[1]證明了所有的圈圖Cn均為邊幻和全標(biāo)號(hào)圖；Wallis等在文獻(xiàn)[8]中證明了所有的皇冠圖Cn⊙K1均是邊幻和全標(biāo)號(hào)圖；Lin等證明了扇圖具有邊幻和全標(biāo)號(hào)[9]；Craft等證明了當(dāng)r為奇數(shù)且圖G(p,q)的點(diǎn)數(shù)p≡4(mod 8)時(shí)，r-正則圖為非邊幻和全標(biāo)號(hào)圖[10]；當(dāng)n≥7時(shí)，完全圖Kn為非邊幻和全標(biāo)號(hào)圖[10]．

文獻(xiàn)[11]總結(jié)了目前所有圖標(biāo)號(hào)的研究現(xiàn)狀，其中的結(jié)論大多數(shù)是針對(duì)特殊圖的．本文主要研究利用標(biāo)號(hào)算法，得到9個(gè)點(diǎn)以內(nèi)的所有圖的標(biāo)號(hào)結(jié)果，通過結(jié)果分析，總結(jié)出若干定理，并猜測(cè)當(dāng)點(diǎn)數(shù)超過9時(shí)，相關(guān)結(jié)論也成立．

1 基本概念

本文所涉及的圖均為無向、簡(jiǎn)單連通圖，具有p個(gè)頂點(diǎn)q條邊的圖記為G(p,q)，當(dāng)q=p-1時(shí)，稱為樹圖；當(dāng)q=p時(shí)，稱為單圈圖；當(dāng)q=p+1時(shí)，稱為雙圈圖．

定義1[1]圖G(p,q)存在雙射f：V(G)∪E(G)→[1，p+q]，使對(duì)G的任意一條邊uv，總有f(u)+f(v)+f(uv)=k，則稱f為圖G的一個(gè)邊幻和全標(biāo)號(hào)(edge-magic total labeling，簡(jiǎn)稱EMTL)，k為幻和常數(shù)．若f(V(G))→[1，p]，則稱為圖G的一個(gè)超級(jí)邊幻和全標(biāo)號(hào)(super edge-magic total labeling，簡(jiǎn)稱SEMTL)．

猜想1[6]每一棵樹有一個(gè)EMTL．

猜想2[7]每一棵樹有一個(gè)SEMTL．

2 EMTL算法

根據(jù)定義1，設(shè)f(u)+f(v)+f(uv)=k，將所有的邊相加，得到

(1)

(2)

使用式(2)無法構(gòu)建解空間，本文將所有邊的標(biāo)號(hào)系數(shù)設(shè)為0，并進(jìn)行累加，故得到了

(3)

這里f(ej)表示邊標(biāo)號(hào)．

算法思想：

(1)計(jì)算圖G的度序列、常數(shù)C和系數(shù)Coe(vi)．

(2)初始化f(vi)，即給點(diǎn)按度從大到小分配標(biāo)號(hào)．

(3)根據(jù)式(3)，如存在正整數(shù)k使等式成立，則進(jìn)入分配函數(shù)Labeling，若不成立，則對(duì)Coe(vi)與邊系數(shù)0組成的序列Coe做一次全排列．

(4)若分配函數(shù)Labeling分配成功，則表示該圖存在EMTL，算法結(jié)束；若分配失敗，則繼續(xù)對(duì)Coe做一次全排列．

(5)直到分配成功或者所有的全排列做完，則算法結(jié)束．若全排列做完后該圖還未標(biāo)號(hào)成功，則表示該圖為NEMTL圖．

EMTL算法：

輸入：圖G(p,q)鄰接矩陣

輸出：圖G(p,q)標(biāo)號(hào)矩陣

1 fori：1→p+q

2 Num[i]=i；

3 End for

4 CalculateCoe()；//計(jì)算Coe(vi)

5 isContinue=true；

6 while isContinue

7 Sum=Calculate Sum(Coe，f(vi))；

8 If((Sum+C)%q==0)

9 if(Allocation(0，0，matrix，Coe，f(vi)))

10 isSuccess=true；

11 isContinue=false；

12 End if

13 End if

14 permutation(Coe)；

15 End while

Allocation (0，0，matrix，Coe，f(vi))函數(shù)用來分配點(diǎn)、邊的標(biāo)號(hào)．

利用遞歸算法來分配標(biāo)號(hào)，需遵守以下原則：

(1)遞歸出口為當(dāng)前函數(shù)層數(shù)n超過了矩陣的行數(shù)，則分配成功，返回true．

(2)當(dāng)給當(dāng)前層的頂點(diǎn)分配元素時(shí)，若該元素已被分配，則start++．

(3)當(dāng)給當(dāng)前層的頂點(diǎn)分配元素時(shí)，若該元素與之前分配過的元素存在邊，則計(jì)算該條邊的標(biāo)號(hào)，若邊標(biāo)號(hào)存在于邊集合中，則刪除當(dāng)前元素，若不存在，則start++．

(4)若當(dāng)前層的元素取值start超過當(dāng)前層元素的個(gè)數(shù)，則退回上一層．

(5)如第一層的元素取值超過第一層元素個(gè)數(shù)，則退出，分配失敗，返回false．

Allocation (0，0，matrix)函數(shù)描述：

輸入：層數(shù)n，初始位置start，當(dāng)前層的矩陣matrix；

輸出：如果存在則輸出EMTL，否則輸出NEMTL．

1 If(n>=L_Matrix>Getlength(0))

2 LabelMatrix=L_Matrix；

3 return true；

4 End if

5 isContinue=true；

6 While isContinue

7 conflict = false；

8 if (start大于當(dāng)前行所填元素個(gè)數(shù))

9 isSuccess=false；

10 End if

11 if (當(dāng)前元素填入矩陣產(chǎn)生沖突)

12 start++；

13 else

14 Allocation (n+1，0，T_Matrix)；

15 End if

16 End while

引理1EMTL算法搜索圖G(p,q)的EMTL解空間，如果有解，則圖G(p,q)為EMTL圖，否則為非邊幻和全標(biāo)號(hào)圖(簡(jiǎn)稱NEMTL圖)．

例1表1、2為圖集G(6,10)的系數(shù)變換過程；圖1為矩陣分配過程；圖2為G(6,10)的原圖和標(biāo)號(hào)圖．

根據(jù)式(3)可得圖1的初始系數(shù)如表1所示．

表1 初始系數(shù)

當(dāng)系數(shù)變換為表2時(shí)，存在正整數(shù)k=19，使得式(3)成立．

表2 最終系數(shù)

將系數(shù)分類之后得到5度點(diǎn)標(biāo)號(hào)為1，4度點(diǎn)標(biāo)號(hào)為2，3度點(diǎn)標(biāo)號(hào)為3、4、11，2度點(diǎn)標(biāo)號(hào)為8，將其填入鄰接矩陣，若存在沖突，則該系數(shù)不適合該鄰接矩陣，重新尋找下一組滿足式(3)的系數(shù)組合，如不存在沖突，則該圖標(biāo)號(hào)成功，該圖成功結(jié)果如圖2所示．

3 定理、猜測(cè)和證明

文中所有圖集是根據(jù)文獻(xiàn)[12]提供的算法，生成9個(gè)點(diǎn)內(nèi)的所有非同構(gòu)圖，用鄰接矩陣存儲(chǔ)．

實(shí)驗(yàn)運(yùn)行環(huán)境及硬件配置為

處理器：Intel(R) Core(TM) i7-7700 CPU @ 3.60 GHz；RAM：64.0 GB；開發(fā)環(huán)境：Visual Studio 2017；開發(fā)語言：C#；繪圖工具：Microsoft Visual； Wolfram Mathematica 11；操作系統(tǒng)：Windows 7，64位．

定理1對(duì)于樹圖G(p,q)，當(dāng)2≤p≤9時(shí)，圖G均為SEMTL圖．

證明

(1)對(duì)于樹圖G(p,q)，當(dāng)2≤p≤9時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表3．

表3 樹圖的EMTL結(jié)果(2≤p≤9)

(3)從表3可以看出，階數(shù)小于等于9的樹圖均為EMTL圖，且是SEMTL圖．

(4)圖3為圖G(9,8)的兩個(gè)成功標(biāo)號(hào)示例．

定理2對(duì)于單圈圖G(p,q)，當(dāng)3≤p≤9時(shí)均有EMTL圖．

證明(1)對(duì)于單圈圖G(p,q)，當(dāng)3≤p≤9時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表4．

表4 單圈圖的EMTL數(shù)目(3≤p≤9)

(3)從表4可以看出，階數(shù)小于等于9的單圈圖均有EMTL圖．

(4)圖4為圖G(9,9)的兩個(gè)成功標(biāo)號(hào)示例．

定理3對(duì)于雙圈圖G(p,q)，當(dāng)4≤p≤9時(shí)均有EMTL圖．

證明

(1)對(duì)于雙圈圖G(p,q)，當(dāng)4≤p≤9時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表5．

(3)從表5可以看出階數(shù)小于等于9的雙圈圖均有EMTL圖．

表5 雙圈圖的EMTL數(shù)目 (4≤p≤9)

(4)圖5為圖G(9,10)的兩個(gè)成功標(biāo)號(hào)示例．

定理4對(duì)于圖G(p,q)，當(dāng)5≤p≤9，q=p+2時(shí)，如果p≡1(mod 2)，該類圖均為EMTL圖，如果p≡0(mod 2)，則該類圖存在NEMTL圖．

證明

(1)對(duì)于圖G(p,q)，當(dāng)5≤p≤9，q=p+2時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表6．

表6 圖G(p,p+2)的EMTL結(jié)果 (5≤p≤9)

(3)從表6可以看出圖G(p,q)，當(dāng)5≤p≤9，q=p+2時(shí)，如果p≡1(mod 2)，該類圖均為EMTL圖，如果p≡0(mod 2)，則該類圖存在NEMTL圖．

(4)圖6為圖G(7,9)和圖G(9,11)成功標(biāo)號(hào)示例，圖7為圖G(6,8)和圖G(8,10)所有的NEMTL圖．

猜測(cè)1對(duì)于圖G(p,q)，當(dāng)p≥10，q=p+2時(shí)，如果p≡1(mod 2)，該類圖均為EMTL圖，如果p≡0(mod 2)，則該類圖存在NEMTL圖．

當(dāng)點(diǎn)數(shù)小于等于11時(shí)，猜測(cè)1所表示的圖集結(jié)果如表7所示．

表7 圖G(p,p+2)的EMTL結(jié)果(10≤p≤11)

從表7的結(jié)果圖集中可以看出，當(dāng)10≤p≤11時(shí)符合猜測(cè)1．

定理5對(duì)于圖G(p,q)，當(dāng)5≤p≤9，q=p+3時(shí)均有EMTL圖．

證明

(1)對(duì)于圖G(p,q)，當(dāng)5≤p≤9，q=p+3時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表8．

表8 圖G(p,p+3)的EMTL結(jié)果(5≤p≤9)

(3)從表8可以看出圖G(p,q)，當(dāng)5≤p≤9，q=p+3時(shí)均有EMTL圖．

(4)圖8為圖G(7,10)、G(8,11)、G(9,12)成功標(biāo)號(hào)示例．

猜測(cè)2對(duì)于圖G(p,q)，當(dāng)p≥10，q=p+3時(shí)均有EMTL圖．

當(dāng)點(diǎn)數(shù)小于等于11時(shí)，猜測(cè)2所表示的圖集結(jié)果如表9所示．

表9 圖G(p,p+3)的EMTL結(jié)果(10≤p≤11)

從表9的結(jié)果圖集中可以看出，當(dāng)10≤p≤11時(shí)符合猜測(cè)2．

定理6對(duì)于圖G(p,q)，當(dāng)5≤p≤9，q=p+4時(shí)，除圖9外均為EMTL圖．

證明

(1)對(duì)于圖G(p,q)，當(dāng)5≤p≤9，q=p+4時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果表10．

(3)從表10可以看出圖G(p,q)，當(dāng)5≤p≤9，q=p+4時(shí)，除圖9外均為EMTL圖．

表10 圖G(p,p+4)的EMTL結(jié)果(5≤p≤9)

(4)圖10為圖G(7,11)、G(8,12)、G(9,13)成功標(biāo)號(hào)示例．

猜測(cè)3對(duì)于圖G(p,q)，當(dāng)p≥10，q=p+4時(shí)，均為EMTL圖．

當(dāng)點(diǎn)數(shù)小于等于11時(shí)，猜測(cè)3所表示的圖集結(jié)果如表11所示．

表11 圖G(p,p+4)的EMTL結(jié)果(10≤p≤11)

從表11的結(jié)果圖集中可以看出，當(dāng)10≤p≤11時(shí)符合猜測(cè)3．

定理7對(duì)于圖G(p,q)，當(dāng)5≤p≤9，q=p+5時(shí)均有EMTL圖．

證明

(1)對(duì)于圖G(p,q)，當(dāng)5≤p≤9，q=p+5時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表12．

表12 圖G(p,p+5)的EMTL結(jié)果(5≤p≤9)

(3)從表12可以看出圖G(p,q)，當(dāng)5≤p≤9，q=p+5時(shí)均有EMTL圖．

(4)圖11為圖G(7,12)、G(8,13)、G(9,14)成功標(biāo)號(hào)示例．

猜測(cè)4對(duì)于圖G(p,q)，當(dāng)p≥10，q=p+5時(shí)均有EMTL圖．

定理8對(duì)于圖G(p,q)，當(dāng)6≤p≤9，q=p+6時(shí)，如果p≡1(mod 2)，該類圖中不存在NEMTL圖，如果p≡0(mod 2)，則該類圖存在NEMTL圖．

證明

(1)對(duì)于圖G(p,q)，當(dāng)6≤p≤9，q=p+6時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表13．

表13 圖G(p,p+6)的EMTL結(jié)果(6≤p≤9)

(3)從表13可以看出圖G(p,q)，當(dāng)6≤p≤9，q=p+6時(shí)，如果p≡1(mod 2)，該類圖中不存在NEMTL圖，如果p≡0(mod 2)，則該類圖存在NEMTL圖．

(4)圖12為圖G(p,p+6)成功標(biāo)號(hào)示例．

猜測(cè)5對(duì)于圖G(p,q)，當(dāng)p≥10，q=p+6時(shí)，如果p≡1(mod 2)，該類圖中不存在NEMTL圖，如果p≡0(mod 2)，則該類圖存在NEMTL圖．

定理9對(duì)于圖G(p,q)，當(dāng)6≤p≤9，q=p+7時(shí)，均為EMTL圖，且不存在SEMTL圖．

證明

(1)對(duì)于圖G(p,q)，當(dāng)6≤p≤9，q=p+7時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表14．

表14 圖G(p,p+7)的EMTL結(jié)果(6≤p≤9)

(3)從表14可以看出圖G(p,q)，當(dāng)6≤p≤9，q=p+7時(shí)均為EMTL圖，且不存在SEMTL圖．

(4)圖13為圖G(7,14)、G(8,15)、G(9,16)成功標(biāo)號(hào)示例．

猜測(cè)6對(duì)于圖G(p,q)，當(dāng)p≥10，q=p+7時(shí)，均為EMTL圖，且不存在SEMTL圖．

定理10對(duì)于圖G(p,q)，當(dāng)6≤p≤9，q=p+8時(shí)，如果p≡0(mod 2)，該類圖均為EMTL圖，如果p≡1(mod 2)，則該類圖存在NEMTL圖．

證明

(1)對(duì)于圖G(p,q)，當(dāng)6≤p≤9，q=p+8時(shí)，根據(jù)式(2)判斷每個(gè)圖理論上是否存在無解．

(2)利用EMTL算法，得到結(jié)果見表15．

(3)從表15可以看出圖G(p,q)，當(dāng)6≤p≤9，q=p+8時(shí)，如果p≡0(mod 2)，該類圖均為EMTL圖，如果p≡1(mod 2)，則該類圖存在NEMTL圖，且只有一個(gè)非邊幻和全標(biāo)號(hào)圖．

表15 圖G(p,p+8)的EMTL結(jié)果(6≤p≤9)

(4)圖14為圖G(6,14)、G(7,15)、G(8,16)、G(9,17)成功標(biāo)號(hào)的邊幻和全標(biāo)號(hào)圖及圖G(7,15)、G(9,17)圖集中的非邊幻和全標(biāo)號(hào)圖．

猜測(cè)7對(duì)于圖G(p,q)，當(dāng)p≥10，q=p+8時(shí)，如果p≡0(mod 2)，該類圖均為EMTL圖，如果p≡1(mod 2)，則該類圖存在NEMTL圖．

4 結(jié) 語

本文設(shè)計(jì)了一種EMTL算法，引入目標(biāo)函數(shù)進(jìn)行優(yōu)化并采用遞歸的方式進(jìn)行標(biāo)號(hào)分配．使用該算法對(duì)9個(gè)點(diǎn)以內(nèi)的所有簡(jiǎn)單連通圖進(jìn)行計(jì)算并得到所有圖的EMTL或NEMTL結(jié)果，通過分析發(fā)現(xiàn)，當(dāng)圖G(p,q)滿足一定條件時(shí)，該類圖有EMTL或NEMTL圖，給出了10個(gè)定理，并給出相關(guān)猜測(cè)．由于圖集較大，故驗(yàn)證了部分圖集，結(jié)果證明部分猜測(cè)當(dāng)10≤p≤11時(shí)也是成立的．