幾類特殊圖的一般指標集

姬玉榮 , 劉金萌

(1.河南理工大學 數學與信息科學學院, 河南 焦作 454000；2.河南工業和信息化職業學院 基礎部, 河南 焦作 454000)

0 引言

令G=(V(G),E(G))為一簡單連通圖，V(G)和E(G)分別是圖G的頂點集和邊集。一個頂點標號函數f:V(G)→Z2誘導出一個邊標號函數f*:E(G)→Z2，滿足f*(v1v2)=f(v1)+f(v2)，?v1v2∈E(G)。 對于每一個i∈Z2，若f(u)=i，則稱頂點u為一個i-點。若f*(e)=i，則稱邊e為一條i-邊。令vf(i)=|{v∈V(G):f(v)=i}|，ef*(i)=|{e∈E(G):f*(e)=i}|。如果|vf(1)-vf(0)|≤1，則稱標號函數f是友好的。CHARTRAND等在文獻[1]中給出了友好指標集的概念，集合FI(G)={|ef*(1)-ef*(0)|:f是友好的}稱為圖G的友好指標集。關于圖的友好指標集，可參閱文獻[2-8]。SHIU和LING[9]把友好指標集推廣到了全友好指標集。 圖G的全友好指標集為FFI(G)={ef*(1)-ef*(0):f是友好的}。若將i-點的集合記作Vi,i∈Z2，那么V0、V1就構成圖G的一個二劃分。在圖的劃分理論中，友好標號又被稱為平衡劃分[10-11]，它在并行計算、大規模集成設計等領域有著廣泛的應用。從算法[12]的角度來看，確定圖友好標號中1邊的最大值或最小值是NP困難的。研究者主要集中在一些特定圖的研究上。例如，SINHA和KAUR[13]研究了Kn、Cn、Fn、F2,m和P3×Pn的全友好指標集；SHIU和LING[9]確定了兩個圈的笛卡爾積的全友好指標集；SHIU和WONG[14]研究了圓柱圖的全友好指標集；SHIU和HO[15]確定了一些Petersen圖的全友好指標集，并且在文獻[16]中確定了細圓柱圖和扁圓柱圖的全友好指標集。

本文把全友好指標集的概念推廣到一般指標集。令G=(V(G),E(G))為一簡單連通圖，任意一個頂點標號函數f:V(G)→Z2誘導出一個邊標號函數f*:E(G)→Z2，其中?v1v2∈E(G)，有f*(v1v2)=f(v1)+f(v2)。

定義圖的一般指標集為GI(G)={ef*(1)-ef*(0):|vf(1)-vf(0)|=m},m<|V(G)|。由于ef*(1)-ef*(0)=2ef*(1)-|E(G)|,所以計算GI(G)就只需要求集合

am(G)={ef*(1):|vf(1)-vf(0)|=m,

m<|V(G)|}。

因此GI(G)={2i-|E(G)|:i∈am(G)}。本文給出圈、路和Cn×P2的一般指標集。

在不引起混淆的情況下，把vf(i)和ef*(i)中的下標省略。

引理1G=(V(G),E(G))是簡單連通圖，令A={e(1)-e(0):v(1)-v(0)=m}，B={e(1)-e(0):v(0)-v(1)=m}，C={e(1)-e(0):|v(1)-v(0)|=m},則

(1)A=B；

(2)當m≥0時，A=B=C。

證明(1) 對任意的x∈A，存在f1滿足vf1(1)-vf1(0)=m使得

令f2(v)=1-f1(v)，則

vf2(1)-vf2(0)=vf1(0)-vf1(1)=-m，

由于所有0-點和所有1-點的標號進行了互換，因此0-邊和1-邊的數目不發生改變，有ef2*(1)-ef2*(0)=x，所以x∈B。同理可得，對任意x∈B，有x∈A，故A=B。

(2)當m≥0時，C=A∪B=A=B，所以A=B=C。證畢。

由引理1知，am(G)={ef*(1):vf(1)-vf(0)=m,0≤m<|V(G)|}。

1 圈的一般指標集

引理2[16](握手引理) 任一圖中

引理3 令f是圖G頂點的任意一個0、1標號函數，G中包含一個圈子圖Cn，如果Cn中含有一條1-邊，那么Cn中的1-邊數一定是偶數。

證明把Cn中標i的頂點集合記為Vi,i∈Z2，e(V1)表示V1中所有邊的數目，e(V1,V0)表示一個頂點在V1中，另一個頂點在V0中所有邊的數目。對于集合V1,運用引理2可以得到，

2|V1|=e(V1,V0)+2e(V1)，

所以e(V1,V0)一定是偶數。因此，Cn中的1-邊數一定是偶數。證畢。

定理1 GI(Cn)={4-n,8-n,12-n,…,n-2m}。

證明因為0≤m

令v(1)-v(0)=m，由v(1)+v(0)=n，得

因為Cn是2-正則圖，所以一個0-點最多只能和2條1-邊相鄰。因此Cn中的1-邊數e(1)≤n-m。

容易計算v(1)-v(0)=m，e(1)=i,i∈{2,4,6,…,n-m}。結合引理3，得到GI(Cn)={4-n,8-n,12-n,…,n-2m}。證畢。

2 路的一般指標集

定理2 GI(Pn)=

證明把Pn中的頂點依次記為v1,v2,…,vn。令v(1)-v(0)=m，由v(1)+v(0)=n，得

e(1)≤min{n-m,n-1}。

容易計算v(1)-v(0)=0,e(1)=i,i∈{2,4,6,…,n-2}。

容易計算v(1)-v(0)=0，e(1)=i-1,i∈{2,4,6,…,n}。所以GI(Pn)={{2i-n+1:i=1,2,3,…,n-1,n是偶數，m=0}。

(2)其他情況

容易計算v(1)-v(0)=m,e(1)=i,i∈{2,4,6,…,n-m}。

容易計算v(1)-v(0)=m，e(1)=i-1,i∈{2,4,6,…,n-m}。所以GI(Pn)={2i-n+1:i=1,2,3,…,n-m,其他情況}。綜上可以得到,當n是偶數，m=0時，GI(Pn)={2i-n+1:i=1,2,3,…,n-m-1}；對于其他情況，則，GI(Pn)={2i-n+1:i=1,2,3,…,n-m}。證畢。

3 Cn×P2的一般指標集

當v(1)-v(0)=m時，記e(i)為em(i),i=0,1。

引理4Cn×P2中1-邊數目em(1)的奇偶性與其1-點數v(1)的奇偶性一致。

證明在Cn×P2中，v(1)-v(0)=m，把標i的頂點集合記為Vi,i∈Z2，V1中0-邊數記為em(0)。em(1)表示一個頂點在V1中、另一個頂點在V0中所有邊的數目，這些邊即是Cn×P2中的所有1-邊。對于集合V1運用引理2可以得到，

3v(1)=2em(0)+em(1)。

所以em(1)的奇偶性與v(1)的奇偶性一致。證畢。

下面利用標號子圖嵌入法，得到Cn×P2的全友好指標集。先給出相關定義。

定義1 圖G在友好標號f下,若e(1)=a，則定義該標號圖為G(a)。

定義3 將標號圖G(a)的兩條邊uv和u′v′替換為長度為2的路uxv和u′x′v′，并連接x和x′，所得到的新標號圖G(b)的過程，稱為一個K2-嵌入，記為G(b)=G(a)⊕K2。若頂點u、x、v、u′、x′、v′的標號分別為b1、a1、b2、b3、a2、b4，把這個K2-嵌入記為

定義4 將標號圖G(a)的兩條邊uv和u′v′替換為長度為3的路uxyv和u′x′y′v′，并連接x和x′、y和y′ ,所得到的新標號圖G(b)的過程，稱為一個C4-嵌入，記為G(b)=G(a)⊕C4。若頂點u、x、y、v、u′、x′、y′、v′的標號分別為b1、a1、a2、b2、b3、a3、a4、b4，把這個C4-嵌入記為

在下面的討論中，在Cn×P2上所有的K2-嵌入或C4-嵌入都是對于圈上的邊uiui+1和vivi+1進行的嵌入，其中i∈{1,…,n},

un+1=u1,vn+1=v1。

為了敘述方便，下面給出一些子結構。

用Ai表示Cn×P2一個標號的C4方格，用e′(1)表示方格插入嵌入后1-邊的變化數。

把不同的C4標號記為

把不同的K2標號記為

由上述(1)～(10)的結論得到下面的引理。

引理5 任給i∈{1,2,3,4,5},存在j∈{1,2,3,4}，使得e′(Ai⊕Bj)=3。

引理6 任給i∈{2,4,5},存在j∈{1,2,3,4}，使得e′(Ai⊕Bj)=1。

引理7[17]當m≥2時，C2n×P2中e0(1)∈{2i：i∈[2,3n]{3n-1}}。C2n+1×P2中e0(1)∈{2i+1：i∈[2,3n]}。

引理8 在C2n×P2中，a2(C2n×P2)={5,7,9,…,6n-9,6n-7,6n-5,6n-3}，a4(C2n×P2)={4,6,8,…,6n-8,6n-6}，其中am(C2n×P2)={e(1):v(1)-v(0)=m,0≤m<2n}。

證明由引理7知,a0(C2n×P2)={4,6,8,…,6n-6,6n-4,6n},那么在C2(n-1)×P2的友好標號下，a0(C2(n-1)×P2)={4,6,8,…,6n-10,6n-6}。在C2(n-1)×P2的某一個方格中進行一個Bj-嵌入，其中j∈{1,2,3,4}。即嵌入的4個頂點中3個標1-點、1個標0-點。在C2(n-1)×P2的任意友好標號下，必存在A1、A2、A3、A4、A5方格，在Ai中嵌入Bj，由引理5得

{7,9,…,6n-7,6n-3}?a2(C2n×P2)。

在C2(n-1)×P2的某個友好標號下，其1-邊數為4時，必存在方格A5，嵌入B1，使得e′(A5⊕B1)=1，所以5∈a2(C2n×P2)。在C2(n-1)×P2的某個友好標號下，其1-邊數為6n-6時，必存在方格A4，嵌入B2，使得e′(A4⊕B2)=1，所以6n-5∈a2(C2n×P2)。

易知1?a2(C2n×P2)、3?a2(C2n×P2)和6n-1?a2(C2n×P2)，結合引理4得，a2(C2n×P2)={5,7,9,…,6n-9,6n-7,6n-5,6n-3}。

因此在C2(n-1)×P2中，a2(C2(n-1)×P2)={5,7,9,…,6n-11,6n-9}。在C2(n-1)×P2的某一個方格中進行一個Bj-嵌入，其中j∈{1,2,3,4}。即嵌入的4個頂點中3個標1-點、1個標0-點。在C2(n-1)×P2中必存在A1、A2、A3、A4、A5方格，在Ai中嵌入Bj，由引理5知，

{8,10,…,6n-8,6n-6}?a4(C2n×P2)。

在C2(n-1)×P2中滿足v(1)-v(0)=2標號下，其1-邊數為5時，不可能只存在方格A1和方格A3，所以必存在方格A2或者A4或者A5，嵌入Bj,由引理6得，6∈a4(C2n×P2)。在C2n×P2中滿足v(1)-v(0)=4標號下，4∈a4(C2n×P2)，2?a4(C2n×P2)。 結合引理4得，a4(C2n×P2)={4,6,8,…,6n-8,6n-6}。證畢。

定理3 GI(C2n×P2)=

證明1)m≡0(mod 4)

易知1?am+2(C2n×P2)和3?am+2(C2n×P2)，結合引理4得，

am+2(C2n×P2)=

因此在C2(n-1)×P2的頂點標號下，若v(1)-v(0)=m+2，其1-邊數目的集合為

am+2(C2(n-1)×P2)=

2)m≡2(mod 4)

類似地,可以得到當m≡2(mod 4)時，

綜上可以證得定理結論。證畢。

類似地,還可以得到如下定理。

定理4 GI(C2n+1×P2)=

4 結束語

本文對圖的全友好指標集的概念進行了推廣，利用嵌入的方法，解決了幾類特殊圖的一般指標集問題。后續有望對圖的一般指標集進行深入研究，得到更一般的構造方法和結論。