完全網絡圖的出邊-平衡指數集

熊曉蓓, 白雨杰, 毋述斐

(1.河南理工大學 數學與信息科學學院, 河南 焦作 454003; 2.河北張家口蔚縣西合營中學, 河北 張家口 075700)

圖的標號問題是離散數學與理論計算機科學領域中的一個重要研究課題,其主要通過對圖的頂點或邊進行標號,進而研究圖的各種內在特性.標號理論的研究成果被廣泛應用于編碼理論、X-射線晶體學、雷達、天文學、電路設計、通信網絡尋址、數據庫管理和網絡密碼等領域[1-3].

邊-友好標號及邊-平衡指數集的概念首先由Kong和Lee在文獻[4]所提出.從算法角度, Chen等[5]人證明了一個圖是邊-平衡的不是NP-難問題. 從集合論角度,學者們通常關注一些特定的圖類, 尋求其邊-平衡指數集.例如, 劉金萌等[6]得到了兩類冪圈嵌套圖的邊-平衡指數集. 鄭玉歌等[7-9]得到了冪圈嵌套網絡圖的邊-平衡指數集. Sinha 和 Kaur[10]得到了星圖,二正則圖,輪圖和圖mPn的邊-平衡指數集, 在文獻[11]中進一步地研究了雙星圖, 扇形和廣義的扇形圖及網格圖P2×Pn的邊-平衡指數集.Shiu[12-13]確定了完全二部圖的邊-平衡指數的極值并進一步確定了完全二部圖的邊-平衡指數集. Vinutha等[14]確定了Cn×P3,Kn,n的邊-平衡指數集. Xing等[15]給出了扇圖的邊-平衡指數集.本文將邊標號的概念推廣到有向圖, 通過對標號矩陣的研究, 確定了友好標號下完全網絡圖的出邊-平衡指數集.

1 預備知識

令G是一個簡單連通圖,它的點集和邊集分別記為V(G)和E(G),如果一個圖既沒有環也沒有平行邊,則稱它為簡單圖.

定義1 稱映射f:E(G)→2為圖G的一個邊標號.用Ef(0),Ef(1)分別表示在映射f作用下標號為0或1的邊集合,用ef(0),ef(1)分別表示這兩個集合的基數.

定義2 設f是圖G的一個邊標號.如果|ef(1)-ef(0)|≤1,則稱標號f是邊-友好的.

令D是一個簡單有向圖,其點集和弧集分別為V(D)和E(D).D的邊標號及邊-友好標號均可按照上述定義得到.對于任意頂點u∈V(D),它的出邊集是指以該頂點為起點的邊集合{uv|v∈V(D),uv∈E(D)}.類似的,入邊集指以該頂點為終點的邊集合{vu|v∈V(D),vu∈E(D)}.下面給出有向圖出邊-平衡指數集的概念,它可看作無向圖邊-平衡指數集概念在有向圖中的推廣.

定義3 設f是有向圖D的一個邊標號.由f誘導出的點標號f+:V(D)→2定義為:?u∈V(D),

對i∈2,標號為i的點稱為i-點.用Vf(0),Vf(1)分別表示0-點或1-點的集合,用vf(0),vf(1)分別表示這兩個集合的基數.

定義4 設D為一有向圖,稱集合{vf(1)-vf(0)∶f是邊-友好的}為D的出邊-平衡指數集.

圖1 標號圖

定義5 圖G在邊標號f下的標號矩陣Lf(G)是一個行和列均對應G中的點得到的指示鄰接矩陣,用xij表示第i行第j列的元素,則

由定義5知給定一個圖,它的一個邊標號會對應一個標號矩陣.反之,任意給定一個該圖的標號矩陣我們也能將其還原為圖的一個邊標號.即圖的邊標號與標號矩陣間存在著一個一一對應(雙射).這為我們利用矩陣來研究邊標號問題提供了保證.

其中: 第i行對應點ui,第j列對應點uj,且對任意i,j,xij=0或1.為了便于計算,移除矩陣對角線上的*得到一個新矩陣(仍稱為標號矩陣),將新得到的矩陣記為A,如下所示:

(1)A中的每個元素是1或者0;

(2)eA(1)=eA(0).

設Jm,n是m×n元素全是1的矩陣,Om,n是m×n元素全是0的矩陣,為構造所需的友好矩陣,首先做如下子陣設計, 對于k≥1,令

本文所需矩陣變換,將按照下述操作進行.

步驟B:令B0是一個2s×n的友好矩陣,當1≤i≤s時,矩陣Bi通過矩陣Bi-1交換(Bi-1)i,1和(Bi-1)s+i,1得到.

下面對n取值分4k,4k+1,4k+2,4k+3四種情況進行討論.

情況1：n=4k,k≥1.

由引理1知,0≤s(A)≤4k且s(A)為偶數.對于任意j∈[0,2k],下證存在友好矩陣A使得s(A)=2j.

令A0=(A4k,4k-4|Jk,1?A4,3),顯然s(A0)=0.對A0的k個子矩陣A4,3逐個進行步驟B,可以得到2k個矩陣,其s-值取遍2到4k之間的所有偶數.

這些矩陣對應的s-值為0,2,4.

情況2：n=4k+1,k≥1.

由引理1知,0≤s(A)≤4k且s(A)為偶數.對于任意j∈[0,2k],下證存在友好矩陣A使得s(A)=2j.

當1≤i≤2k時,在矩陣Ai-1基礎上通過交換(Ai-1)i,1和(Ai-1)2k+1+i,1得到矩陣Ai,易得s(Ai)=2i.

這些矩陣對應的s-值為0,2,4.

情況3：n=4k+2,k≥1.

由引理1知,0≤s(A)≤4k+1且s(A)為奇數.對于任意j∈[0,2k],下證存在友好矩陣A使得s(A)=2j+1.

這些矩陣對應的s-值為1,3,5.

情況4：假設n=4k+3.

由引理1, 0≤s(A)≤4k+3且s(A)為奇數.對于任意j∈[0,2k+1], 下證存在友好矩陣A使得s(A)=2j+1.

由引理1和上面四種情況可以得到

3 結束語

通過構造標號圖對應的標號矩陣,利用矩陣變換、子矩陣設計的方法研究了有向圖的邊-友好標號,確定了完全網絡圖的出邊-平衡指數集.由于標號矩陣與標號圖之間存在一一對應,利用指數集證明中所構造的標號矩陣可以很快做出相應的邊標號圖.標號矩陣的方法對于其他圖類的邊-友好標號及邊-平衡指數集的研究或許也有參考價值.