圖類{K2*Pn+2e}的邊-平衡指數集

譚秋月,孫平安,徐梁立,黃立紅

1.武夷學院數學與計算機系,福建武夷山354300

2.廈門大學數學科學學院,福建廈門361005

圖類{K2*Pn+2e}的邊-平衡指數集

譚秋月1,孫平安1,徐梁立1,黃立紅2

1.武夷學院數學與計算機系,福建武夷山354300

2.廈門大學數學科學學院,福建廈門361005

研究了特殊圖類的邊的標號問題，根據字典乘積圖概念定義了{K2*Pn+2e}這種特殊圖類，并利用圖結構的分解和邊標號互換的方法給出了該圖類的平衡指數集的準確值和證明。

邊標號;邊平衡指數集;{K2*Pn+2e}圖類

1 引言

圖的頂點和邊標號問題是一個比較有趣的問題，也是圖論中的熱點問題之一。1992年，Lee等考慮圖的頂點友好標號問題[1]。1995年，Kong和Lee提出了相對應的邊友好標號問題[2]。

定義1設G=(V(G),E(G))為一個簡單圖，映射f為對圖G所有邊的一個{0,1}標號，即f:E(G)→{0,1}，?e∈E(G)，定義f(e)=0或1，在映射f下標號為0或1的邊集記為Ef(0)，Ef(1)，用ef(0)，ef(1)分別來表示此二集合的基數。由f誘導出一個對圖的G部分頂點的{0,1}標號函數f*定義如下:圖G中的任意一個頂點，若關聯的邊中標1的邊數多于標0的邊數時，則頂點標1；若關聯的邊中標1的邊數少于標0的邊數時，則頂點v標0；若關聯的邊中v標1的邊數等于標0的邊數時頂點v不標號。圖G在f誘導出映射f*標號為0或1的頂點集分別記為Vf(0)，Vf(1)，它們的基數分別記為vf(0)，vf(1)。

定義2設f是圖G的邊集E(G)上的一個0、1標號函數，如果|ef(1)-ef(0)|≤1，那么就稱f是圖G的邊-友好標號。

定義3如果f是圖G的邊-友好標號，若在邊-友好標號f下滿足|vf(1)-vf(0)|≤1，則稱f為邊-平衡標號。定義集合{|vf(1)-vf(0)|}，f為圖G的友好標號}為圖G的邊-平衡指數集，記為EBI(G)，記EBI(G)中最大的元素為maxEBI(G)。

2 相關EBI(G)引理

圖G的邊平衡指數集沒有一般的計算公式，文獻[3-6]中計算了Kn×K2、路Pn、圈Cn、完全圖Kn、輪Wn和n-m?bius梯子的EBI(G)，并給出了一下引理：

引理1若圖G的所有頂點都為奇點，則EBI(G)只包含偶數。

引理2若圖G為有p個頂點的r正則圖，圖G存在邊-友好標號f，則

3 結論及其證明

本文所考慮的圖都是有限無向簡單圖。一個圖G對應著一個有序對(V(G)，E(G))，記G=(V(G)，E(G))，V(G)和E(G)分別表示圖G的頂點集和邊集，|V(G)|=p，|E(G)|=q，其他未加說明的術語和符號均引自文獻[7]。首先介紹與本論文有關的圖的一種運算，稱為合成運算。

定義4[7]設G1=(V1,E1)與G2=(V2,E2)是兩個圖，G1關于G2的合成運算，稱為關G1于G2的字典乘積圖(lexicographic product)，記作，以為頂點集，并且以為邊集組成的圖。

定義5設K2=(V1,E1)是2個頂點的完全圖，Pn=(V2,E2)是n(n≥2)個頂點的路圖，以為頂點集，并且以,或u1=u2且(v1,v2)∈E2﹜+2e(其中為邊集組成的圖，稱為正則圖{K2*Pn+2e}(n≥2)。

可見n≥3以后，K2*Pn+2e=K2*Cn。K2*Pn+2e(n≥2)是頂點數為2n，邊數為n(n+2)的(n+2)-正則圖。為了證明方便，對圖類K2*Pn+2e的頂點重新標定，將Pn在K2*Pn+2e中第一行頂點標號為u，u1，L，un-1，Pn在K2*Pn+2e中第二行頂點標號為v，v1，L，vn-1，且uv恰好是K2在K2*Pn+2e中的1個復制，uivi恰好為K2在K2*Pn+2e中的i+1個復制，其中i=1，2，L，n-1，如圖1所示為K2*P2+2e，如圖2所示為K2*P3+2e。

圖1 正則圖{K2*P2+2e}Fig.1 Canonical graph{K2*P2+2e}

圖2 正則圖{K2*P3+2e}Fig.2 Canonical graph{K2*P3+2e}

通過分析圖類K2*Pn+2e(n≥2)的結構，數學歸納法給出圖類{K2*Pn+2e}(n≥2)的maxEBI(G)的邊-友好標號，然后通過邊互換的方式給出EBI(G)的所有元素，得到了以下定理：

定理1圖類{K2*Pn+2e}(n≥2)的邊平衡指數集為：

在證明過程中用f(a,b,c)表示圖G在邊-友好標號f誘導出的頂點標號f*中，標1的頂點數為a個，標0的頂點數為b個，不標號的頂點數為c個，顯然有p=a+b+c。

證明（1）當n=2t時，p=4t，q=4t2+4t，r=2t+2。由引理2知

如下圖3所示對圖類{K2*P2+2e}進行邊-友好標號，對頂點v的邊0,1標號分類為（1001）（0011）（0101）分別對應圖3中(a)(b)(c)的頂點無標號的三種，圖正則且對稱，0,1邊互換后，得到的（0110）（1100）（1010），頂點依然無標號，EBI(G)取不到值。

在圖4中，給出了圖類{K2*P2+2e}的部分邊-友好標號，可見|vf(1)-vf(0)|=0或者1。結合公式（3），得到圖類{K2*P2+2e}的EBI(G)值為0,1，即EBI(G)={0,1}。

圖3 正則圖{K2*P2+2e}Fig.3 Canonical graph{K2*P2+2e}

圖4 正則圖{K2*P2+2e}EBI(G)為0,1的部分情況Fig.4 The partial results ofEBI(G)=0,1 in canonical graph{K2*P2+2e}

當2≤t≤6時，只求出了EBI(G)的最大值

⑦當7≤t≤14時，maxEBI(G)=4t-7；當15≤t時，maxEBI(G)=4t-8。若存在邊友好標號f(a,b,c)，

第一步，記頂點集A={u1，u2，L，u2t-2}，B={v1，v2，L，v2t-2}。給定邊標號的方式f如下：標0的邊是邊uu2t-1，邊uv2t-1，邊vv2t-1，邊u2t-1v（即u和u2t-1及u和B的所有頂點連成的邊，v和v2t-1及v和A的所有頂點連成的邊），邊uiui+j(i=1，2，L，2t-2；j=1，2，L，t-1(mod2t-2))；其他邊都標1；則ef(0)=4+4×(2t-2)+(2t-2)(t-2)=2t2+2t，因此f為邊-友好標好，此時u，v，u2t-1，v2t-1相關聯的邊中各有2t條邊標0，因此f(u)=f(v)=f(u2t-1)=f(v2t-1)=0；ui和vi相關聯的邊中各有k條邊標0，因此f(ui)=f(vi)=1(i=1，2，L，2t-2）。在邊標號的f下，|vf(1)-vf(0)|=4t-8。

第二步，通過邊互換的方式得到EBI(G)中的其他元素。規定將邊互換以后的邊標號稱為g。頂點u,v,u2t-1,v2t-1最多各有t-2條邊0邊變成1邊而仍不改變這些頂點在g下的標號，做互換uvi←→uivi(1，2，L，t-2)，得到EBI(G)值為4t-9，4t-10，L，3t-6的K2*Pn+2e；將邊互換u2t-1vi←→ui-1vi(i=2，3，L，t-1)，得到EBI(G)值為3t-7，3t-8，L，2t-4的K2*P2+2e；將邊互換uiv←→uivi+1(i=t-1，t，L，2t-3)，得到圖K2*Pn+2e類{K2*Pn+2e}的EBI(G)值為t-3，t-4，L，0。

（2）當n=2t+1時，p=4t+2，q=4t2+8t+3，r=2t+3。每個頂點都為奇點，所以不標號的頂點個數應該為0，f(a,b,c)=f(a,b,0)由引理2知，

（i）當n=3，t=1時，p=4t+2=6，q=4t2+8t+3=15，G={K2*P3+2e}，maxEBI(G)≤4，由引理1可知，EBI(G)值只為偶數，又因為|vf(1)+vf(0)|=6，且f為邊友好標號必須滿足|ef(1)-ef(0)|≤1，所以EBI(G)只可能為0，2，4。

若f為邊友好標號，則f(a,b,0)只可能為f(3,3,0)，f(4,2,0)，f(5,1,0)。如圖5（a）-（c）所示，給出圖類{K2*P3+2e}的EBI(G)為0,2,4的情況，所以EBI(G)={0，2，4}。如圖5（d）所示，f(6,0,0)是不可能的。|vf(1)+vf(0)|=6，但是|ef(1)-ef(0)|≤2，而且每個標1的頂點關聯標號為0的邊都達到了臨界值。所以EBI(G)不可能為6。

圖5 正則圖{K2*P3+2e}的EBI(G)為0,2,4的部分情況Fig.5 The partial results ofEBI(G)=0,2,4 in canonical graph{K2*P3+2e}

（ⅱ）當n=5，t=2時，p=4t+2=10，q=4t2+8t+3=35，G=K2*P5+2e，maxEBI(G)≤8，由引理1可知，EBI(G)值只為偶數，又因為|vf(1)+vf(0)|=10，且f為邊友好標號必須滿足|ef(1)-ef(0)|≤1，所以EBI(G)只可能為0,2,4,6,8。若f為邊友好標號，則f(a,b,0)只可能為f(9,1,0),f(8,2,0)，f(7,3,0)，f(6,4,0)和f(5,5,0)。如圖6（a）-（d）所示，給出圖類{K2*P5+2e}的EBI(G)為0,2,4,6的部分情況，所以EBI(G)=﹛0,2,4,6﹜。如圖6（e）所示，要滿足|vf(1)+vf(0)|=10，|vf(1)+vf(0)|=8且|ef(1)-ef(0)|≤1，如果f(a,b,0)=f(9,1,0)時，每個標1的頂點關聯標號為0的邊都達到了臨界值，f(9,1,0)取不到圖，所以EBI(G)不可能為8，圖類{K2*P5+2e}的EBI(G)只可能為0,2,4,6，EBI(G)={0,2,4,6}。在圖6中，由于邊太多，只標0邊，沒有標記的邊標號都為1。

圖6 正則圖{K2*P5+2e}的EBI(G)為0,2,4的部分情況Fig.6 The partial results ofEBI(G)=0,2,4 in canonical graph

當t≥3時，，所以maxEBI(G)=8t-(4t+2)=4t-2。

第一步，記頂點集A={u1，u2，L，u2t}，B={v1，v2，L，v2t}。給定邊標號的方式f如下：標0的邊是邊uv，u和B的所有頂點連成的邊，v和A的所有頂點連成的邊，邊uiuj(i=1，2，L，2t；j=i+1，i+2，L，i+t(mod2t))，其他邊都標1。

第二步，通過邊相互交換的方法得到EBI(G)中的其他元素。規定將邊互換以后的邊標號稱為g。頂點u，v最多各有t-1邊標0邊變成標1邊而仍不改變頂點u，v在g下的標號，做邊的相互交換uvi←→uivi(i=1，2，L，t-1），且由引理1知，得到圖類{K2*Pn+2e}的EBI(G)值只能為偶數4t-4，4t-6，L，2t；做邊的相互交換vui←→uivi(i=t，t+1，L，2t-2)，得到圖類{K2*Pn+2e}的EBI(G)值為2t-2，2t-4，L，2；將邊uiu2t由標0邊變成標1邊，此時ef(0)=4t2+4t+2，可見f仍為邊-友好標好，但此時f(u2t)=0，f(u)=0，因此得到圖類{K2*Pn+2e}的EBI(G)值為0。

4 結語

利用對圖組頂點序列號特征，遞歸到整個圖形，進而給出了圖類{K2*Pn+2e}邊-平衡指數集。

在計算圖的邊平衡指數集方面，本文雖然解決了圖類{K2*Pn+2e}的邊平衡指數集，但花費了較多時間嘗試著去研究是否存在某種等價定義更通用化更一般化的轉化方式使得計算圖的邊平衡指數集更為簡單？目前沒有更好的結果，這一方面可以繼續更深入研究。另一方面，讀者也可以構造和尋找更多的具有良好性質的對稱的圖類，給出這些圖類的頂點和邊的平衡指數集，本文中標號函數的設計方法為其他合成圖、正則圖的研究提供了很好的思路借鑒，所證結果為圖論和編碼理論提供了重要的公式和數據。

[1]Lee SM,Liu AC,Tan SK.On balanced graphs[J].Congr.Numer.,1992,87:59-64

[2]KONG MC,LEE SM.On edge-balanced graphs[J].Graph Theory,Combinatoric and Algorithms,1995(1):711-722

[3]Kong E,Lee SM,Raridan C.On the edge-balanced index sets of product graphs[J/OL].J.Indones.Math.Soc. http://arxiv.org/abs/1103.4994,2011-03-25

[4]Wang TM,Lin CM,Lee SM.On edge-balanced index sets of regular graphs[A].The 26th Workshop on Combinatorial Mathematics and Computation Theory,218-223

[5]Krop E,Sikes K.On the edge-balanced index sets of complete bipartite graphs[J/OL].Arxiv.http://arxiv.org/abs/1106.1085,2011-06-06

[6]Chopra D,Lee SM,Su HH.On edge-balanced index sets of wheels graphs[J].Int.J.Contemp.Math.sciences,2010,5(53):2605-2620

[7]哈拉里F.圖論[M].李蔚萱譯.上海:上海科學技術出版社,1968:26

[8]譚秋月.若干圖類的平衡指標集[J].昆明理工大學學報:自然科學版,2014,39(12):136-140

The Edge-balanced Index Sets of the Graphs{K2*Pn+2e}

TAN Qiu-yue1,SUN Ping-an1,XU Liang-li1,HUANG Li-hong2
1.Department of Mathematics and Computer/Wuyi College,Wuyishan354300,China
2.College of Mathematics Science/Xiamen University,Xiamen361005,China

In this paper,the edge-balance index for some particular graphs was studied.According to the lexicographic product graph concept,the families of the graphs{K2*Pn+2e}were defined and to provide the accurate value and proof for the exact balance index set of the families of the graphs{K2*Pn+2e}with the interchange between the decomposition of the graph structure and the edge label.

Edge label;edge-balanced index set;families of the graph{K2*Pn+2e}

O157.5

:A

:1000-2324(2015)06-0927-05

2014-04-23

:2014-05-06

福建省自然科學基金項目(2013J05006);若干特殊圖類的邊-平衡指標集研究(XL201409);福建省大學生創新創業訓練計劃項目(201510397029);若干圖類友好標號問題的研究(JA15513)

譚秋月(1980-),女,碩士研究生,講師,研究方向為圖論、離散數學.E-mail:tqyspa@163.com