圖(p≤9)的邊幻和全標號

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

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

0 引 言

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

文獻[11]總結了目前所有圖標號的研究現狀，其中的結論大多數是針對特殊圖的．本文主要研究利用標號算法，得到9個點以內的所有圖的標號結果，通過結果分析，總結出若干定理，并猜測當點數超過9時，相關結論也成立．

1 基本概念

本文所涉及的圖均為無向、簡單連通圖，具有p個頂點q條邊的圖記為G(p,q)，當q=p-1時，稱為樹圖；當q=p時，稱為單圈圖；當q=p+1時，稱為雙圈圖．

定義1[1]圖G(p,q)存在雙射f：V(G)∪E(G)→[1，p+q]，使對G的任意一條邊uv，總有f(u)+f(v)+f(uv)=k，則稱f為圖G的一個邊幻和全標號(edge-magic total labeling，簡稱EMTL)，k為幻和常數．若f(V(G))→[1，p]，則稱為圖G的一個超級邊幻和全標號(super edge-magic total labeling，簡稱SEMTL)．

猜想1[6]每一棵樹有一個EMTL．

猜想2[7]每一棵樹有一個SEMTL．

2 EMTL算法

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

(1)

(2)

使用式(2)無法構建解空間，本文將所有邊的標號系數設為0，并進行累加，故得到了

(3)

這里f(ej)表示邊標號．

算法思想：

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

(2)初始化f(vi)，即給點按度從大到小分配標號．

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

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

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

EMTL算法：

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

輸出：圖G(p,q)標號矩陣

1 fori：1→p+q

2 Num[i]=i；

3 End for

4 CalculateCoe()；//計算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))函數用來分配點、邊的標號．

利用遞歸算法來分配標號，需遵守以下原則：

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

(2)當給當前層的頂點分配元素時，若該元素已被分配，則start++．

(3)當給當前層的頂點分配元素時，若該元素與之前分配過的元素存在邊，則計算該條邊的標號，若邊標號存在于邊集合中，則刪除當前元素，若不存在，則start++．

(4)若當前層的元素取值start超過當前層元素的個數，則退回上一層．

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

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

輸入：層數n，初始位置start，當前層的矩陣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大于當前行所填元素個數)

9 isSuccess=false；

10 End if

11 if (當前元素填入矩陣產生沖突)

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圖，否則為非邊幻和全標號圖(簡稱NEMTL圖)．

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

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

表1 初始系數

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

表2 最終系數

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

3 定理、猜測和證明

文中所有圖集是根據文獻[12]提供的算法，生成9個點內的所有非同構圖，用鄰接矩陣存儲．

實驗運行環境及硬件配置為

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

定理1對于樹圖G(p,q)，當2≤p≤9時，圖G均為SEMTL圖．

證明

(1)對于樹圖G(p,q)，當2≤p≤9時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

(4)圖3為圖G(9,8)的兩個成功標號示例．

定理2對于單圈圖G(p,q)，當3≤p≤9時均有EMTL圖．

證明(1)對于單圈圖G(p,q)，當3≤p≤9時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

(4)圖4為圖G(9,9)的兩個成功標號示例．

定理3對于雙圈圖G(p,q)，當4≤p≤9時均有EMTL圖．

證明

(1)對于雙圈圖G(p,q)，當4≤p≤9時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

(4)圖5為圖G(9,10)的兩個成功標號示例．

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

證明

(1)對于圖G(p,q)，當5≤p≤9，q=p+2時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

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

猜測1對于圖G(p,q)，當p≥10，q=p+2時，如果p≡1(mod 2)，該類圖均為EMTL圖，如果p≡0(mod 2)，則該類圖存在NEMTL圖．

當點數小于等于11時，猜測1所表示的圖集結果如表7所示．

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

從表7的結果圖集中可以看出，當10≤p≤11時符合猜測1．

定理5對于圖G(p,q)，當5≤p≤9，q=p+3時均有EMTL圖．

證明

(1)對于圖G(p,q)，當5≤p≤9，q=p+3時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

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

猜測2對于圖G(p,q)，當p≥10，q=p+3時均有EMTL圖．

當點數小于等于11時，猜測2所表示的圖集結果如表9所示．

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

從表9的結果圖集中可以看出，當10≤p≤11時符合猜測2．

定理6對于圖G(p,q)，當5≤p≤9，q=p+4時，除圖9外均為EMTL圖．

證明

(1)對于圖G(p,q)，當5≤p≤9，q=p+4時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

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

猜測3對于圖G(p,q)，當p≥10，q=p+4時，均為EMTL圖．

當點數小于等于11時，猜測3所表示的圖集結果如表11所示．

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

從表11的結果圖集中可以看出，當10≤p≤11時符合猜測3．

定理7對于圖G(p,q)，當5≤p≤9，q=p+5時均有EMTL圖．

證明

(1)對于圖G(p,q)，當5≤p≤9，q=p+5時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

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

猜測4對于圖G(p,q)，當p≥10，q=p+5時均有EMTL圖．

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

證明

(1)對于圖G(p,q)，當6≤p≤9，q=p+6時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

(4)圖12為圖G(p,p+6)成功標號示例．

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

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

證明

(1)對于圖G(p,q)，當6≤p≤9，q=p+7時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

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

猜測6對于圖G(p,q)，當p≥10，q=p+7時，均為EMTL圖，且不存在SEMTL圖．

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

證明

(1)對于圖G(p,q)，當6≤p≤9，q=p+8時，根據式(2)判斷每個圖理論上是否存在無解．

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

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

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

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

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

4 結 語

本文設計了一種EMTL算法，引入目標函數進行優化并采用遞歸的方式進行標號分配．使用該算法對9個點以內的所有簡單連通圖進行計算并得到所有圖的EMTL或NEMTL結果，通過分析發現，當圖G(p,q)滿足一定條件時，該類圖有EMTL或NEMTL圖，給出了10個定理，并給出相關猜測．由于圖集較大，故驗證了部分圖集，結果證明部分猜測當10≤p≤11時也是成立的．