P2×Cn的友好標號集

尤永旦 華 波

(1.浙江師范大學 數(shù)理與信息工程學院，浙江 金華321004;2.東華大學 理學院，上海201620)

0 引言

設圖G是一個簡單圖，由點的標號函數(shù)f:V→Z2,可以誘導出邊的標號函數(shù)f*:E→Z2，使得f*xy=fx+fymod2,?xy∈EG.對任意一個i∈Z2，定義vfi=f-1i和efi=f*-1i.如果vf1-vf0≤1，稱標號函數(shù)f:V→Z2為友好標號函數(shù).我們定義友好指數(shù)FI和全友好指數(shù)FFI指數(shù)如下:

FIG=ef1-ef0f是圖G的一個友好標號函數(shù)，

1 預備知識

定義1.1[1]：給定兩個圖G=V,E和H=V',E'，定義G×H=V×V',E''如下：

E''=v,v',u,u':v.u∈E且v'=u'或者v=u且v'.u'∈E'.

引理1.1[2]：Cm中有i個頂點賦值為1，不妨設1≤2i≤m，用參考文獻[2]求解的方法可知ef1可以取2,4,…,2i.此處的f未必是友好標號函數(shù).

引理1.2：設f是P2×Cn的一個友好標號函數(shù)，當n=2k時候，ef1為偶數(shù)，反之，ef1為奇數(shù).

證明：i,j邊有兩個頂點：一個賦值為i另外一個賦值為j，i,j∈0,1.由引理1.1可知P2×Cn中的兩個圈Cn的ef1為偶數(shù)只要證明兩個圈Cn之間的邊ef1的奇偶性就行.現(xiàn)在考慮設兩個圈Cn之間的邊ef1的奇偶性，設在其中一個圈Cn中點賦值為1有i,其中2i≤n，在這個Cn中點賦值為0有n-i，在另外一個圈Cn中點賦值為1有n-i，并且點賦值為0有i，設兩圈之間有j條1,1邊其中j≤mini,n-i，則就會也有j條0,0邊，所以在這個兩個圈之間的0,1邊的邊數(shù)為n-2j，所以引理1.2成立.

引理1.3：

當n≡0mod4時，F(xiàn)IP2×Cn?3n,3n-4,…,8,4,0，

當n≡2mod4時，F(xiàn)IP2×Cn?3n,3n-4,…,10,6,2，當n=2k+1時，F(xiàn)IP2×Cn?3n,3n-2,…,5,3,1.

證明：顯然ef1+ef0=EP2×Cn=3n.

因此得知當n≡0mod4時，F(xiàn)IP2×Cn?3n,3n-4,…,8,4,0，

當n≡2mod4時，F(xiàn)IP2×Cn?3n,3n-4,…,10,6,2，

根據(jù)引理1.2，當n=2k+1時候，ef1為奇數(shù)，同理可知當n≡2k+1，F(xiàn)IP2×Cn?3n,3n-2,…,5,3,1.

2 主要結果

定理2.1：

當n≡0mod4時，F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,8,4,0，

當n≡2mod4時，F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,10,6,2當n=2k+1時，F(xiàn)IP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

證明：

若n=2j，由引理1.2可知在圖P2×Cn中ef1為偶數(shù).當f是友好標號函數(shù)時，則在圖P2×Cn中ef1為偶數(shù).且可證ef1取到大部分偶數(shù)，證明如下：

構造使得ef1=4的友好標號函數(shù)

構造使得ef1=3n的友好標號函數(shù)

e1可取到4,6,8,…,2n-2,2n,3n,

可證P2×Cn中ef1≠2.

若有兩個圈C1=u1,1u1,2u1,3…u1,n，C2=u2,1u2,2u2,3…u2,n的邊賦值都為0，則根據(jù)友好標號函數(shù)可知兩個圈的點賦值一個賦值為0，另外一個賦值為1，則ef1=n≥4，若有一個圈(不妨設為C1=u1,1u1,2u1,3…u1,n)中有邊賦值為1，因為圈邊賦值為1為偶數(shù)所以這個圈中邊賦值至少為偶數(shù)，又根據(jù)友好標號函數(shù)，則在另外一個圈中必然也是邊賦值1的條也是偶數(shù)并且在這個圈中ef1≥2，所以在P2×Cn中ef1≠2.

又可證P2×Cn中ef0≠2.

第一種情形若ef0=2的邊全在圈C1中，則邊賦值為0的邊(不妨設邊u1,iu1,i+1)必然與下面一個圈C2中u2,i，u2,i+1兩點組成一個小圈，則可得出在這個小圈中ef0=2或者4.同理在另外一個小圈ef0=2或者4，則就會出現(xiàn)ef0≠2，假設矛盾.

第二種情形ef0=2都不在圈C1，C2中不妨設邊u1,iu2,i，u1,ju2,j，1+i≤j為1，圈C3=u1,iu2,iu2,i-1u1,i-1這樣可知道是在圈C3,圈C4與圈C5=u1,iu2,iu2,i+1…u

2,ju1,ju1,j-1u1,j-2…u1,i+1，1+i≤j中每個圈的ef0至少為2，所以得出ef0≠2與假設矛盾.因為

ef1≠2,ef0≠2可知3n-4?FIP2×Cn.因為e1=4,6,8,…,2n-2,2n,3n，e1≠2,e0≠2，再根據(jù)根據(jù)引理1.3,所以當n≡2mod4時，F(xiàn)IP2×Cn=3n，3n-8,3n-12,…,8,4,0.

當n≡2mod4時，F(xiàn)IP2×Cn=3n，3n-8,3n-12,…,10,6,2.

斷言1：若n=2j+1，則在圖P2×Cn中ef1為取到大部分奇數(shù).證明如下：

由引理1.2在圖P2×Cn中e1為奇數(shù)，構造使得ef1=5的友好標號函數(shù)

構造使得ef1=7的友好標號函數(shù)

現(xiàn)在已經(jīng)構造友好標號函數(shù)使得e1=5,7,…,2n+1,

這樣就有ef0=2,4,…,n-1，根據(jù)ef1+ef0=EP2×Cn=3n，可知ef1=3n-2,3n-4,…,2n+1,所以我們已經(jīng)構造出ef1=5,7,…,2n+1,…,3n-4,3n-2.

斷言2：ef1≠1，其中f為P2×Cn的友好標號函數(shù).

若在P2×Cn中ef1=1，邊賦值為1在下面C1=u1,1u1,2u1,3…u1,n，C2=u2,1u2,2u2,3…u2,n中的某個圈中，不妨設C1=u1,1u1,2u1,3…u1,n，則根據(jù)引理1.1可知邊賦值為1至少兩條，與假設矛盾，若都不在這兩個圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n，則邊賦值為1在圈C1與圈C2之間的連接處，不妨設點u1,1=0，u2,1=1，則在C3=u1,1u2,1u2,2u1,2中，根據(jù)引理2.1可知邊賦值為1至少兩條，所以P2×Cn中ef1≠1.

斷言3：當n≥5時，ef1≠3，其中f為P2×Cn的友好標號函數(shù).

若有兩個圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n邊賦值為都為0，則根據(jù)友好標號函數(shù)可知C1=u1,1u1,2u1,3…u1,n的點都賦值為0，C2=u2,1u2,2u2,3…u2,n的點都賦值為1；或者C1=u1,1u1,2u1,3…u1,n的點都賦值為1，C2=u2,1u2,2u2,3…u2,n的點都賦值為0，則e1=n≥5.

若有一個圈C1=u1,1u1,2u1,3…u1,n中邊賦值為1，根據(jù)引理1.1可知圈邊賦值為1的邊數(shù)為偶數(shù)，所以在這個圈C1中ef1≥2，又根據(jù)友好標號函數(shù)，則在C2=u2,1u2,2u2,3…u2,n中必然也是邊賦值1且為偶數(shù)條，而且在這個圈C2中ef1≥2，所以ef1≥4≠3.

斷言4：ef0≠1ef0≠3，其中f為P2×Cn的友好標號函數(shù).

因為由引理1.2可知e1為奇數(shù)，所以可知在該圖中e0為偶數(shù)，所以e0≠1e0≠3明顯成立.

當n=2k+3時，k∈1,2,3,…，因為e1=5,7,9,…,2n-7,…,3n-2，

e1≠3,e0≠3，e1≠1,e0≠1,顯然這個等式e1=3n不成立(由引理1.1可知在奇圈中e1也是偶數(shù)而e1=3n這個是奇數(shù)).

當n=2k+3，n∈1,2,3,…時，F(xiàn)IP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

當n=3時，ef1≠1，ef1≠3n=9，ef1=3,5,7，所以FIP2×C3=5,3,1.

所以當n=2k+1時，F(xiàn)IP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.

參考文獻：

[1]J A Bandy, U S R Murty.Graph Theory with Application[M].Springer International Publisher,2007.

[2] N Cairnie ， K Edwards.The computational complexity of cordial and equitable labeling[J].Discrete Math,2000,216:29-34.

Abstract： Friendly index set is a common problem in the labeling problem. The present paper researches the friendly index set of graphP2×Cn.

Keywords：friendly labeling function; FI; FFI; circle