幾種叉積圖的平衡指標集

陳碧英

（武夷學院 數(shù)學與計算機學院，福建 武夷山 354300）

1 預備知識

定義 1.1[2]設 f:V（G）→ ｛0，1｝是圖 G 的一個頂點標號映射,則由f可誘導出圖G的一個部分邊的標號 f*:E（G ）→｛0，1｝，對任意的 uν∈ E（G）,當且僅當f（u）=f（ν）時，有 f*（uν）=f（u）；若 f（u）≠ f（ν），則邊 uν未被 f* 標號.稱 Bf（G）=ef（1）-ef（0）為圖 G 的平衡標號。

定義 1.2[2]稱圖G的這個標號 f為友好標號；稱 BI （G為友好標號｝為圖G的平衡指標集。

定義 1.3[3]設 f:V（G）→ ｛0，1｝是圖 G 的一個點標號映射，定義 g:V（G）→｛-0.5,0.5｝，其中 g=f-0.5.則由g誘導出相應的邊標號映射g*:E （G）→ ｛-1,0，1｝，g*（uν）=g（u）+g（ν）,? uν∈ E（G ）。

命題1.1[3]若記 νg（i)為在點標號 g下V（G）中標號為i的頂點數(shù)，eg（i)為在g導出的邊標號g*下E （G ）中標號為 i的邊數(shù)，Bg（G）=eg（1）-eg（-1）。因此g*（e）=-1 等價于 f*（e）=0，g*（e）=1 等價于 f*（e）=1，g*（e）=0等價于在 f中 e不標號。

命題 1.2[3]f為友好標號等價于≤1,g為友好標號。

命題1.3[3]對于圖G的一個｛-0.5，0.5｝標號，記

引理 1.1[3]若 g為 G=｛V（G）,E（G）｝的任意一個｛-0.5,0.5｝標號，則有

定義 1.4 稱一個圖是（r,s）-正則的（r≠ s），如果這個圖的每個點的度數(shù)都是r或者s。

命題 1.4[3]若 G=｛V（G）,E（G）｝為（r,s）-正則圖，g為 G 的任意一個｛-0.5，0.5｝標號，則：

定理1.1[3]若g為r-正則G的任意一個｛-0.5，0.5｝標號，則 Bg（G ）（其中分別表示度為r的點中標號為0.5和-0.5的點的數(shù)目。）

定義 1.5 稱一個圖是（r,s,t）-正則的 （r≠s≠ t），如果這個圖的每個點的度數(shù)都是r或者s，或者t。

命題 1.5 若 G＝（V,E）為 （r,s,t）-正則圖，g 為 G的任意一個｛-0.5，0.5｝標號，則：

定義1.5 稱一個圖是 （r,s,t,y）-正則的 （r≠s≠t≠y），如果這個圖的每個點的度數(shù)都是r或者s，或者t，或者 y。

命題 1.6 若 G＝（V,E）為（r,s,t,y）-正則圖，g 為 G的任意一個｛-0.5，0.5｝標號，則

設 G1＝（V1,E1）與 G2＝（V2,E2）是兩個圖,G1與 G2的叉積圖定義為：G1×G2=（V,E），其中

且（ν1，ν2）∈E2｝

注意到任意圖G的平衡指標集為非負整數(shù)集合。為了書寫的方便，對于非負整數(shù)a，b且a＜b，通常用［a，b］來表示［a，b］的所有整數(shù)，即若 BI（G ）=［a，b］，則BI（G）=｛a，a+1，…,b-1,b｝。

Km,n為完全二部圖，Cn為n個頂點的圈，Pn為 n個頂點的路，Wn為n個頂點的輪圖。在參考文獻[4-5]中給出 Cm×Cn和 P2×Pn的平衡指標集。

2 若干叉積圖的平衡指標集

定理 2.1 BI（Wm×Wm）=

證明：(1)m=2 時 W2×W2是 4-正則圖。

W2×W2共有9個點，設g為友好標號，則Bg（W2×W2）∈ ｛±2｝故 BI（W2×W2）=｛2｝。

(2)m=3 時，W3×W3是 9-正則圖。

W3×W3共有6個點，設g為友好標號，則

Bg（W3×W3）＝0.故 BI（W3×W3）=｛0｝。

(3)m≥ 4 時，Wm×Wm是（9,3m,m2）-正則圖，其中9度點有m2個，3m度點有2m個，m2度點有1個。

設 r=9,s=3m,t=m2，則

Wm×Wm共有（m+1）2個點，由于 m≥ 4 時，m2≥ 2m+1。取遍每一個值，Wm×Wm都存在友好標號。

當（m+1）2為偶數(shù)時，即m為奇數(shù)時，設g為友好標號，則

引理2.1 設A≥2為一正整數(shù)，則

證明：用數(shù)學歸納法來證.

（1）當 A=2 時，2a=0,2,4,則 2a+3b 可以取 0,2,4（b=0）;3,5,7（b=1）;6,8,10（b=2）;9,11,13（b=3）;12,14,16（b=4）… 3b0-6,3b0-4,3b0-2（b=b0-2）;3b0-3,3b0-1,3b0+1（b=b0-1）;3b0,3b0+2,3b0+4（b=b0）。

因 此，2a+3b取遍 了 0,2,3,4,5,6… ,3b0-3,3b0-2,3b0-1,3b0,3b0+1,3b0+2,3b0+4.故此時結(jié)論成立。

（2）假設結(jié)論對A≤k-1成立，下證結(jié)論對A=k也成立。

當 a＜k 時，2a+3b 可以取 0,2,3,… ,2（k-1）+3b0-2,2（k-1）+3b0。

當a=k時，2a+3b可以取2k,2k+3,2k+6,…,2k+3(b0-1),2k+3b0。

故2a+3b所有可能的取值為0,2,3,…,2k+3b0-3,2k+3b0-2,2k+3b0所以命題成立。

定理 2.4 BI（K2,m×K1,m）=證明：（1）m=1 時，P3×P2是（1,2）正則圖，其中 1

度點有4個，2度點有2個。設r=1，s=2則故 Bg（P3×P2）∈ ［-1，1］。故 BI（P3×P2）=｛0,1｝。

(2)m=2 時，K2,2×K1,2是（2,4）-正則圖，其中 2 度點有8個，4度點有4個。

設r=2,s=4則

其中：V+g,4∈ ［0，4］。

故 Bg（K2,2×K1,2）∈ ｛0，±2，±4｝。故 BI（K2,2×K1,2）=｛0，2，4｝。

(3)m=3 時，K2,3×K1,3是（2,3,9）- 正則圖，其中 2 度點有12個，3度點有6個，9度點有2個。

設 r=2,s=3,t=9，則

故 Bg（K2,3×K1,3）∈ ［-10,10］。故 BI（K2,3×K1,3）=[0,10]。

(4）m≥ 4 時，K2,m×K1,m是 （2,m,2m,m2）正則圖，其中2度點有m2個，m度點有2m個，2m度點有m個，m2度點有2個。

故 Bg（K2,3×K2,3）∈ ［-18,18］{±17}。

故 BI（K2,3×K2,3）∈ ［0,18］{17}。

(4）m=4 時，K2,4×K2,4是 （4,8,16）-正則圖，其中 4度點有16個，8度點有16個，16度點有4個。

設 r=4,s=8,t=16，則

一個值時，K2,m×K2,m都存在友好標號。

當m2+4m+4為偶數(shù)時，即m為偶數(shù)時，設g為友好標號，則

故 Bg（K2,m×K2,m）∈{0，±（2m-4）,±2（2m-4）,… ,±（3m+2）（2m-4）}。

故 BI（K2,m×K2,m）∈ {0，2m-4,2（2m-4）,…,（3m+2）（2m-4）}。

當m2+4m+4為奇數(shù)時，即m為奇數(shù)時，設g為友好標號，則

故 Bg（K2,m×K2,m）∈ {±2,±（m-2）±2,±2（m-2）±2,… ,±（6m+4）（m-2）±2}。

3 結(jié)論

通過證明得到 Wn×Wn，Cm×Cn，K1,m×K1,m，K2,m×K1,m，K2,m×K2,m叉積圖的平衡指標集的準確值。