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

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

1.武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)系,福建武夷山354300

2.廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院,福建廈門361005

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

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

1.武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)系,福建武夷山354300

2.廈門大學(xué)數(shù)學(xué)科學(xué)學(xué)院,福建廈門361005

研究了特殊圖類的邊的標(biāo)號問題，根據(jù)字典乘積圖概念定義了{(lán)K2*Pn+2e}這種特殊圖類，并利用圖結(jié)構(gòu)的分解和邊標(biāo)號互換的方法給出了該圖類的平衡指數(shù)集的準(zhǔn)確值和證明。

邊標(biāo)號;邊平衡指數(shù)集;{K2*Pn+2e}圖類

1 引言

圖的頂點(diǎn)和邊標(biāo)號問題是一個(gè)比較有趣的問題，也是圖論中的熱點(diǎn)問題之一。1992年，Lee等考慮圖的頂點(diǎn)友好標(biāo)號問題[1]。1995年，Kong和Lee提出了相對應(yīng)的邊友好標(biāo)號問題[2]。

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

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

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

2 相關(guān)EBI(G)引理

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

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

引理2若圖G為有p個(gè)頂點(diǎn)的r正則圖，圖G存在邊-友好標(biāo)號f，則

3 結(jié)論及其證明

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

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

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

可見n≥3以后，K2*Pn+2e=K2*Cn。K2*Pn+2e(n≥2)是頂點(diǎn)數(shù)為2n，邊數(shù)為n(n+2)的(n+2)-正則圖。為了證明方便，對圖類K2*Pn+2e的頂點(diǎn)重新標(biāo)定，將Pn在K2*Pn+2e中第一行頂點(diǎn)標(biāo)號為u，u1，L，un-1，Pn在K2*Pn+2e中第二行頂點(diǎn)標(biāo)號為v，v1，L，vn-1，且uv恰好是K2在K2*Pn+2e中的1個(gè)復(fù)制，uivi恰好為K2在K2*Pn+2e中的i+1個(gè)復(fù)制，其中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)的結(jié)構(gòu)，數(shù)學(xué)歸納法給出圖類{K2*Pn+2e}(n≥2)的maxEBI(G)的邊-友好標(biāo)號，然后通過邊互換的方式給出EBI(G)的所有元素，得到了以下定理：

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

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

證明（1）當(dāng)n=2t時(shí)，p=4t，q=4t2+4t，r=2t+2。由引理2知

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

在圖4中，給出了圖類{K2*P2+2e}的部分邊-友好標(biāo)號，可見|vf(1)-vf(0)|=0或者1。結(jié)合公式（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}

當(dāng)2≤t≤6時(shí)，只求出了EBI(G)的最大值

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

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

第二步，通過邊互換的方式得到EBI(G)中的其他元素。規(guī)定將邊互換以后的邊標(biāo)號稱為g。頂點(diǎn)u,v,u2t-1,v2t-1最多各有t-2條邊0邊變成1邊而仍不改變這些頂點(diǎn)在g下的標(biāo)號，做互換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）當(dāng)n=2t+1時(shí)，p=4t+2，q=4t2+8t+3，r=2t+3。每個(gè)頂點(diǎn)都為奇點(diǎn)，所以不標(biāo)號的頂點(diǎn)個(gè)數(shù)應(yīng)該為0，f(a,b,c)=f(a,b,0)由引理2知，

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

若f為邊友好標(biāo)號，則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，而且每個(gè)標(biāo)1的頂點(diǎn)關(guān)聯(lián)標(biāo)號為0的邊都達(dá)到了臨界值。所以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}

（ⅱ）當(dāng)n=5，t=2時(shí)，p=4t+2=10，q=4t2+8t+3=35，G=K2*P5+2e，maxEBI(G)≤8，由引理1可知，EBI(G)值只為偶數(shù)，又因?yàn)閨vf(1)+vf(0)|=10，且f為邊友好標(biāo)號必須滿足|ef(1)-ef(0)|≤1，所以EBI(G)只可能為0,2,4,6,8。若f為邊友好標(biāo)號，則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)時(shí)，每個(gè)標(biāo)1的頂點(diǎn)關(guān)聯(lián)標(biāo)號為0的邊都達(dá)到了臨界值，f(9,1,0)取不到圖，所以EBI(G)不可能為8，圖類{K2*P5+2e}的EBI(G)只可能為0,2,4,6，EBI(G)={0,2,4,6}。在圖6中，由于邊太多，只標(biāo)0邊，沒有標(biāo)記的邊標(biāo)號都為1。

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

當(dāng)t≥3時(shí)，，所以maxEBI(G)=8t-(4t+2)=4t-2。

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

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

4 結(jié)語

利用對圖組頂點(diǎn)序列號特征，遞歸到整個(gè)圖形，進(jìn)而給出了圖類{K2*Pn+2e}邊-平衡指數(shù)集。

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

[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].李蔚萱譯.上海:上?？茖W(xué)技術(shù)出版社,1968:26

[8]譚秋月.若干圖類的平衡指標(biāo)集[J].昆明理工大學(xué)學(xué)報(bào):自然科學(xué)版,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

福建省自然科學(xué)基金項(xiàng)目(2013J05006);若干特殊圖類的邊-平衡指標(biāo)集研究(XL201409);福建省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201510397029);若干圖類友好標(biāo)號問題的研究(JA15513)

譚秋月(1980-),女,碩士研究生,講師,研究方向?yàn)閳D論、離散數(shù)學(xué).E-mail:tqyspa@163.com