尤永旦 華 波
(1.浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華321004;2.東華大學(xué) 理學(xué)院,上海201620)
設(shè)圖G是一個簡單圖,由點的標(biāo)號函數(shù)f:V→Z2,可以誘導(dǎo)出邊的標(biāo)號函數(shù)f*:E→Z2,使得f*xy=fx+fymod2,?xy∈EG.對任意一個i∈Z2,定義vfi=f-1i和efi=f*-1i.如果vf1-vf0≤1,稱標(biāo)號函數(shù)f:V→Z2為友好標(biāo)號函數(shù).我們定義友好指數(shù)FI和全友好指數(shù)FFI指數(shù)如下:
FIG=ef1-ef0f是圖G的一個友好標(biāo)號函數(shù),
定義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,不妨設(shè)1≤2i≤m,用參考文獻(xiàn)[2]求解的方法可知ef1可以取2,4,…,2i.此處的f未必是友好標(biāo)號函數(shù).
引理1.2:設(shè)f是P2×Cn的一個友好標(biāo)號函數(shù),當(dāng)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)在考慮設(shè)兩個圈Cn之間的邊ef1的奇偶性,設(shè)在其中一個圈Cn中點賦值為1有i,其中2i≤n,在這個Cn中點賦值為0有n-i,在另外一個圈Cn中點賦值為1有n-i,并且點賦值為0有i,設(shè)兩圈之間有j條1,1邊其中j≤mini,n-i,則就會也有j條0,0邊,所以在這個兩個圈之間的0,1邊的邊數(shù)為n-2j,所以引理1.2成立.
引理1.3:
當(dāng)n≡0mod4時,F(xiàn)IP2×Cn?3n,3n-4,…,8,4,0,
當(dāng)n≡2mod4時,F(xiàn)IP2×Cn?3n,3n-4,…,10,6,2,當(dāng)n=2k+1時,F(xiàn)IP2×Cn?3n,3n-2,…,5,3,1.
證明:顯然ef1+ef0=EP2×Cn=3n.
因此得知當(dāng)n≡0mod4時,F(xiàn)IP2×Cn?3n,3n-4,…,8,4,0,
當(dāng)n≡2mod4時,F(xiàn)IP2×Cn?3n,3n-4,…,10,6,2,
根據(jù)引理1.2,當(dāng)n=2k+1時候,ef1為奇數(shù),同理可知當(dāng)n≡2k+1,F(xiàn)IP2×Cn?3n,3n-2,…,5,3,1.
定理2.1:
當(dāng)n≡0mod4時,F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,8,4,0,
當(dāng)n≡2mod4時,F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,10,6,2當(dāng)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ù).當(dāng)f是友好標(biāo)號函數(shù)時,則在圖P2×Cn中ef1為偶數(shù).且可證ef1取到大部分偶數(shù),證明如下:
構(gòu)造使得ef1=4的友好標(biāo)號函數(shù)
構(gòu)造使得ef1=3n的友好標(biāo)號函數(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ù)友好標(biāo)號函數(shù)可知兩個圈的點賦值一個賦值為0,另外一個賦值為1,則ef1=n≥4,若有一個圈(不妨設(shè)為C1=u1,1u1,2u1,3…u1,n)中有邊賦值為1,因為圈邊賦值為1為偶數(shù)所以這個圈中邊賦值至少為偶數(shù),又根據(jù)友好標(biāo)號函數(shù),則在另外一個圈中必然也是邊賦值1的條也是偶數(shù)并且在這個圈中ef1≥2,所以在P2×Cn中ef1≠2.
又可證P2×Cn中ef0≠2.
第一種情形若ef0=2的邊全在圈C1中,則邊賦值為0的邊(不妨設(shè)邊u1,iu1,i+1)必然與下面一個圈C2中u2,i,u2,i+1兩點組成一個小圈,則可得出在這個小圈中ef0=2或者4.同理在另外一個小圈ef0=2或者4,則就會出現(xiàn)ef0≠2,假設(shè)矛盾.
第二種情形ef0=2都不在圈C1,C2中不妨設(shè)邊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與假設(shè)矛盾.因為
ef1≠2,ef0≠2可知3n-4?FIP2×Cn.因為e1=4,6,8,…,2n-2,2n,3n,e1≠2,e0≠2,再根據(jù)根據(jù)引理1.3,所以當(dāng)n≡2mod4時,F(xiàn)IP2×Cn=3n,3n-8,3n-12,…,8,4,0.
當(dāng)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ù),構(gòu)造使得ef1=5的友好標(biāo)號函數(shù)
構(gòu)造使得ef1=7的友好標(biāo)號函數(shù)
現(xiàn)在已經(jīng)構(gòu)造友好標(biāo)號函數(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)構(gòu)造出ef1=5,7,…,2n+1,…,3n-4,3n-2.
斷言2:ef1≠1,其中f為P2×Cn的友好標(biāo)號函數(shù).
若在P2×Cn中ef1=1,邊賦值為1在下面C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n中的某個圈中,不妨設(shè)C1=u1,1u1,2u1,3…u1,n,則根據(jù)引理1.1可知邊賦值為1至少兩條,與假設(shè)矛盾,若都不在這兩個圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n,則邊賦值為1在圈C1與圈C2之間的連接處,不妨設(shè)點u1,1=0,u2,1=1,則在C3=u1,1u2,1u2,2u1,2中,根據(jù)引理2.1可知邊賦值為1至少兩條,所以P2×Cn中ef1≠1.
斷言3:當(dāng)n≥5時,ef1≠3,其中f為P2×Cn的友好標(biāo)號函數(shù).
若有兩個圈C1=u1,1u1,2u1,3…u1,n,C2=u2,1u2,2u2,3…u2,n邊賦值為都為0,則根據(jù)友好標(biāo)號函數(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ù)友好標(biāo)號函數(shù),則在C2=u2,1u2,2u2,3…u2,n中必然也是邊賦值1且為偶數(shù)條,而且在這個圈C2中ef1≥2,所以ef1≥4≠3.
斷言4:ef0≠1ef0≠3,其中f為P2×Cn的友好標(biāo)號函數(shù).
因為由引理1.2可知e1為奇數(shù),所以可知在該圖中e0為偶數(shù),所以e0≠1e0≠3明顯成立.
當(dāng)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ù)).
當(dāng)n=2k+3,n∈1,2,3,…時,F(xiàn)IP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.
當(dāng)n=3時,ef1≠1,ef1≠3n=9,ef1=3,5,7,所以FIP2×C3=5,3,1.
所以當(dāng)n=2k+1時,F(xiàn)IP2×Cn=3n-4,3n-8,3n-10,3n-12…,5,3,1.
參考文獻(xiàn):
[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