圖2n的奇優(yōu)美及其奇強(qiáng)協(xié)調(diào)性

林育青

(汕頭職業(yè)技術(shù)學(xué)院自然科學(xué)系,廣東 汕頭 515041)

林育青

(汕頭職業(yè)技術(shù)學(xué)院自然科學(xué)系,廣東 汕頭 515041)

該文定義了圖并研究了該圖的奇優(yōu)美和奇強(qiáng)協(xié)調(diào)性.利用構(gòu)造法分別給出了圖在n=4k(k≥2)、n=4k+2時(shí)的奇優(yōu)美算法,在n=4k(k≥2)時(shí),的奇強(qiáng)協(xié)調(diào)算法,進(jìn)而證明了圖在n=2k(k≥3)時(shí)是奇優(yōu)美圖,在n=4k(k≥2)時(shí)是奇強(qiáng)協(xié)調(diào)圖等結(jié)論,從而推動(dòng)了對(duì)圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性的研究.最后提出猜想:當(dāng)n=4k+2時(shí),圖不是奇強(qiáng)協(xié)調(diào)圖.

奇優(yōu)美圖;奇強(qiáng)協(xié)調(diào)圖;圖

1 引言

優(yōu)美圖的提出始于1963年文獻(xiàn)[1]的一個(gè)猜想,由于它的趣味性和廣泛的應(yīng)用性,一直以來(lái)深受人們的重視.1982年,文獻(xiàn) [2]引入圖的強(qiáng)協(xié)調(diào)標(biāo)號(hào),1994年,Gnanajoethi提出猜想:“每棵樹(shù)都是奇優(yōu)美的”[3]．推動(dòng)了對(duì)圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性的研究,目前已有很多這方面的結(jié)果[4-11],但由于缺乏一個(gè)系統(tǒng)和有力的工具,迄今,只能對(duì)一些特殊圖類(lèi)探索其奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性.

定理 1.1當(dāng)n=2k(k≥3)時(shí),圖是奇優(yōu)美圖.

定理 1.2當(dāng)n=4k(k≥2)時(shí),圖是奇強(qiáng)協(xié)調(diào)圖.

定義 1.1在含有n個(gè)頂點(diǎn)的圈 Cn中,當(dāng)且僅當(dāng)兩頂點(diǎn)的距離為2時(shí)增加一條邊,這樣得到的圖稱(chēng)為在含有 n個(gè)頂點(diǎn)的圈中,當(dāng)且僅當(dāng)兩頂點(diǎn)的距離為 2時(shí)增加一條長(zhǎng)度為 2的路,這樣得到的圖稱(chēng)為圖 C2n的細(xì)分圖,記為圖設(shè) U={u1,u2,…,un}是圖 Cn的頂點(diǎn)集,V={v1,v2,…,vn}是圖所增加的頂點(diǎn)集,其中,增加的路依次記為:u1v1u3,u2v2u4,…,unvnu2;則圖的頂點(diǎn)集為:U∪V.

定義 1.2[12]一個(gè)簡(jiǎn)單圖 G=(V,E)稱(chēng)為奇優(yōu)美的,如果存在一個(gè)單射,f:V(G)→{0,1,2,…,2|E|?1}對(duì)所有邊 uv=e∈E(G),由 f?(uv)=|f(u)?f(v)|導(dǎo)出的映射,有：f?:V(G)→{1,3,…,2|E|?1}是一個(gè)一一對(duì)應(yīng),f稱(chēng)為G的奇優(yōu)美標(biāo)號(hào).

定義 1.3[2]一個(gè)簡(jiǎn)單圖 G=(V,E)稱(chēng)為奇強(qiáng)協(xié)調(diào)的,如果存在一個(gè)單射f:V(G)→{0,1,2,…,2|E|?1},對(duì)所有邊 uv=e∈E(G),由 f?(uv)=f(u)+f(v)導(dǎo)出的映射,有：f?:V(G)→{1,3,…,2|E|?1}是一個(gè)一一對(duì)應(yīng),f稱(chēng)為G的奇強(qiáng)協(xié)調(diào)標(biāo)號(hào).

為敘述方便,本文規(guī)定所討論的圖都是無(wú)向簡(jiǎn)單圖,為敘述方便,v表示點(diǎn) v,uv表示邊,f(v)表示點(diǎn)v的標(biāo)號(hào),簡(jiǎn)單的記為v=f(v);同理,f(uv)表示邊uv的標(biāo)號(hào),也簡(jiǎn)單的記為uv=f(uv)．

點(diǎn)v2p稱(chēng)為偶點(diǎn),v2p?1稱(chēng)為奇點(diǎn)．其他未加說(shuō)明的定義和符號(hào)均來(lái)自文獻(xiàn)[13]．

(1)u2i?1=2i?2,i=1,2,…,2k;

(2)u2i=24k?2i+1,i=1,2,…,k;u2i=24k?2i?1,i=k+1,…,2k;

(3)v1=16k?1;v2i?1=8k?2i+1,i=2,…,k;

v2i?1=8k?2i?1,i=k+1,…,2k;

(4)v2i=8k+2i+2,i=1,2,…,2k.

按照標(biāo)號(hào)A可得如下結(jié)果:

引理 2.1圖中各頂點(diǎn)的標(biāo)號(hào)均不相同,即圖的頂點(diǎn)集與集合{0,1,2,…,24k?1}構(gòu)成單射.

證明首先,由標(biāo)號(hào)A可得,圖的頂點(diǎn)集中各頂點(diǎn)的標(biāo)號(hào)大于等于零,小于等于24k?1.其次,由(1)、(2)得,頂點(diǎn)u1,u2,…,u4k中奇點(diǎn)的標(biāo)號(hào)均為偶數(shù),偶點(diǎn)的標(biāo)號(hào)均為奇數(shù),所以U={u1,u2,…,u4k}中各頂點(diǎn)的標(biāo)號(hào)均不相同;由(3)、(4)得,頂點(diǎn)v1,v2,…,v4k中奇點(diǎn)的標(biāo)號(hào)均為奇數(shù),偶點(diǎn)的標(biāo)號(hào)均為偶數(shù),所以V={v1,v2,…,v4k}中各頂點(diǎn)的標(biāo)號(hào)均不相同.另外,對(duì)于頂點(diǎn)U={u1,u2,…,u4k}中的奇點(diǎn)與V={v1,v2,…,v4k}中的偶點(diǎn),若存在i,j,使得u2i?1=v2j,即2i?2=8k+2j+2,從而有i?j=4k+2,與i,j=1,2,…,2k矛盾;對(duì)于頂點(diǎn)U={u1,u2,…,u4k}中的偶點(diǎn)與V={v1,v2,…,v4k}中的奇點(diǎn),若存在i,j,使得u2i=v1或u2i=v2j?1,即有24k?2i±1=16k?1或24k?2i±1=8k?2j±1,從而有:i=4k、i=4k?1或i?j=8k±1、i?j=8k,這都與i,j相應(yīng)的取值范圍矛盾,由此U={u1,u2,…,u4k}中各頂點(diǎn)與V={v1,v2,…,v4k}中各頂點(diǎn)的標(biāo)號(hào)均不相同.

引理 2.2圖中各邊的標(biāo)號(hào)均不相同.即圖的邊集與集合{1,3,…,24k?1}構(gòu)成一一對(duì)應(yīng).

證明我們把邊的標(biāo)號(hào)分為三大類(lèi)來(lái)考慮.

(一)由標(biāo)號(hào)A的(1)、(2)可知,u1u2…u4ku1中邊的標(biāo)號(hào)有以下幾種情況：

(1)u2i?1u2i=|24k?2i+1?(2i?2)|=24k?4i+3,i=1,2,…,k;

(2)u2iu2i+1=|24k?2i+1?[2(i+1)?2]|=24k?4i+1,i=1,2,…,k;

(3)u2i?1u2i=|24k?2i?1?(2i?2)|=24k?4i+1,i=k+1,k+2,…,2k;

(4)u2iu2i+1=|24k?2i?1?[2(i+1)?2]|=24k?4i?1,i=k+1,k+2,…,2k?1;

(5)u4ku1=20k?1;

(二)由標(biāo)號(hào) A的 (1)、(3)可知邊 u2i?1v2i?1及v2i?1u2i+1(或v4k?1u1)的標(biāo)號(hào)有以下幾種情況：

(1)u1u1=16k?1;

(2)u2i?1v2i?1=|8k?2i+1?(2i?2)|=8k?4i+3,i=2,3,…,k;

(3)u2i?1v2i?1=|8k?2i?1?(2i?2)|=8k?4i+1,i=k+1,k+2,…,2k;

(4)v1u3=16k?3;

(5)v2i?1u2i+1=|8k?2i+1?[2(i+1)?2]|=8k?4i+1,i=2,3,…,k;

(6)v2i?1u2i+1=|8k?2i?1?[2(i+1)?2]|=8k?4i?1,i=k+1,k+2,…,2k?1;

(7)v4k?1u1=4k?1;

(三)由標(biāo)號(hào)A的(2)、(4)可知邊u2iv2i及v2iu2i+2(或v4ku2)的標(biāo)號(hào)有以下幾種情況：

(1)u2iv2i=|24k?2i+1?(8k+2i+2)|=16k?4i?1,i=1,2,…,k;

(2)u2iv2i=|24k?2i?1?(8k+2i+2)|=16k?4i?3,i=k+1,k+2,…,2k;

(3)v2iu2i+2=|24k?2(i+1)+1?(8k+2i+2)|=16k?4i?3,i=1,2,…,k?1;

(4)v2iu2i+2=|24k?2(i+1)?1?(8k+2i+2)|=16k?4i?5,i=k,k+1,…,2k?1;

(5)v4ku2=12k?3.

首先,由(一)易知,在u1u2…u4ku1中,各邊的標(biāo)號(hào)均為奇數(shù),都是以4為公差的等差數(shù)列,且范圍為:

(1)20k+3≤u2i?1u2i≤24k?1,i=1,2,…,k;

(2)20k+1≤u2iu2i+1≤24k?3,i=1,2,…,k;

(3)16k+1≤u2i?1u2i≤20k?3,i=k+1,k+2,…,2k;

(4)16k+3≤u2iu2i?1≤20k?5,i=k+1,k+2,…,2k?1;

(5)u4ku1=20k?1;

由邊的標(biāo)號(hào)范圍及等差數(shù)列的性質(zhì)知,在u1u2…u4ku1中各邊的標(biāo)號(hào)不相等.

其次,由(二)易知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k?1u1)中,各邊的標(biāo)號(hào)也均為奇數(shù)且都是以4為公差的等差數(shù)列,且范圍為:

(1)u1u1=16k?1;

(2)4k+3≤u2i?1v2i?1≤8k?5,i=2,3,…,k;

(3)1≤u2i?1v2i?1≤4k?3,i=k+1,k+2,…,2k;

(4)v1u3=16k?3;

(5)4k+1≤v2i?1u2i+1≤8k?7,i=2,3,…,k;

(6)3≤v2i?1u2i+1≤4k?5,i=k+1,k+2,…,2k?1;

(7)v4k?1u1=4k?1;

同樣,由邊的標(biāo)號(hào)范圍及等差數(shù)列的性質(zhì)知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k?1u1)中各邊的標(biāo)號(hào)不相等.

再次,由(三)易知,在邊u2iv2i及 v2iu2i+2(或v4ku2)中,各邊的標(biāo)號(hào)也均為奇數(shù)且都是以4為公差的等差數(shù)列,且范圍為:

(1)12k?1≤u2iv2i≤16k?5,i=1,2,…,k;

(2)8k?3≤u2iv2i≤12k?7,i=k+1,k+2,…,2k;

(3)12k+1≤v2iu2i+2≤16k?7,i=1,2,…,k?1;

(4)8k+3≤v2iu2i+2≤12k?5,i=k,k+1,…,2k?1;

(5)v4ku2=12k?3.

同樣,由邊的標(biāo)號(hào)范圍及等差數(shù)列的性質(zhì)知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4ku2)中各邊的標(biāo)號(hào)不相等.

由上知,三類(lèi)邊的標(biāo)號(hào)范圍互不重疊,故也互不相等.

(1)u2i?1=12k?8,i=1,2,…,k+1;u2i?1=24k?12i+24,i=k+2,k+3,…,2k+1;

(2)u2i=24k?12i+21,i=1,2,…,k;u2i=21i?1,i=k+1,k+2,…,2k+1;

(3)v2i=24k?12i+17,i=1,2,…,k;v2k+1=12k+1,v2i?1=12k?5,i=k+2,k+ 3,…,2k+1;

(4)v2i=12k+6,i=1,2,…,k;v2i=24k?12i+14,v4k+2=0,i=k+1,k+2,…,2k.

按照標(biāo)號(hào)B可得如下結(jié)果：

引理 2.3圖中各頂點(diǎn)的標(biāo)號(hào)均不相同,即圖的頂點(diǎn)集與集合{0,1,2,…,24k+11}構(gòu)成單射.

證明首先,由標(biāo)號(hào)B可得,圖的頂點(diǎn)集中各頂點(diǎn)的標(biāo)號(hào)大于等于零,小于等于24k+11.其次,由(1)(2)得,頂點(diǎn)u1,u2,…,u4k+2中奇點(diǎn)的標(biāo)號(hào)均為偶數(shù),偶點(diǎn)的標(biāo)號(hào)均為奇數(shù),所以U={u1,u2,…,u4k+2}中各頂點(diǎn)的標(biāo)號(hào)均不相同;由(3)(4)得,頂點(diǎn)v1,v2,…,v4k+2中奇點(diǎn)的標(biāo)號(hào)均為奇數(shù),偶點(diǎn)的標(biāo)號(hào)均為偶數(shù),所以V={v1,v2,…,v4k+2}中各頂點(diǎn)的標(biāo)號(hào)均不相同.另外,對(duì)于頂點(diǎn)U={u1,u2,…,u4k+2}中的奇點(diǎn)與V={v1,v2,…,v4k+2}中的偶點(diǎn),若存在i,j,使得u2i?1=v2i或u2i?1=v4k+2,即

或12i?8=0或24k?12i+24=12j+6或24k?12i+24=24k?12j+14或24k?12i+24=0,從而有

或3i=2或2i+2j=4k+3或6i?6j=5或i=2k+2,這都與奇偶性質(zhì)或i的取值范圍矛盾;對(duì)于頂點(diǎn)U={u1,u2,…,u4k}中的偶點(diǎn)與V={v1,v2,…,v4k}中的奇點(diǎn),若存在i,j,u2i=v2j?1或u2i=v2k+1,即有

或

或

從而有

或

或

這都與i,j相應(yīng)的取值范圍或奇偶性質(zhì)矛盾,由此U={u1,u2,…,u4k+2}中各頂點(diǎn)與V= {v1,v2,…,v4k+2}中各頂點(diǎn)的標(biāo)號(hào)均不相同.綜上所述,圖中各頂點(diǎn)的標(biāo)號(hào)均不相同,即圖的頂點(diǎn)集與集合{0,1,2,…,24k+11}構(gòu)成單射.

引理2.4圖中各邊的標(biāo)號(hào)均不相同.即圖的邊集與集合{1,3,…,24k+ 11}構(gòu)成一一對(duì)應(yīng).

證明我們把邊的標(biāo)號(hào)分為三大類(lèi)來(lái)考慮.

(一)由標(biāo)號(hào)B的(1)(2)可知u1u2…u4k+2u1中邊的標(biāo)號(hào)有以下幾種情況:

(1)u2i?1u2i=|24k?12i+21?(12i?8)|=24k?24i+29,i=1,2,…,k;

(2)u2iu2i+1=|24k?12i+21?[12(i+1)?8]|=24k?24i+17,i=1,2,…,k;

(3)u2k+1u2k+2=|12(k+1)?8?[12(k+1)?1]|=7;

(4)u2i?1u2i=|24k?12i+24?(12i?1)|=24i?24k?25,i=k+2,k+3,…,2k+1;

(5)u2iu2i+1=|24k?12(i+1)+24?(12i?1)|=24i?24k?13,i=k+1,k+2,…,2k;

(6)u4k+2u1=|12(2k+1)?1?4|=24k+7;

(二)由標(biāo)號(hào)B的(1)(3)可知邊u2i?1v2i?1及v2i?1u2i+1(或v4k+1u1)的標(biāo)號(hào)有以下幾種情況:

(1)u2i?1v2i?1=|24k?12i+17?(12i?8)|=24k?24i+25,i=1,2,…,k;

(2)u2k+1v2k+1=|12(k+1)?8?12(k+1)|=3;

(3)u2i?1v2i?1=|24k?12i+24?(12i?5)|=24i?24k?29,i=k+2,k+3,…,2k+1;

(4)v2i?1u2i+1=|24k?12i+17?[12(i+1)?8]|=24i?24k+13,i=1,2,…,k;

(5)v2k+1u2k+1=|24k?12(k+2)+24?(12k+1)|=1;

(6)v2i?1u2i+1=|24k?12(i+1)+24?(12i?5)|=24i?24k?17,i=k+2,k+3,…,2k;

(7)v4k+1u1=|12(2k+1)?5?4|=24k+3;

(三)由標(biāo)號(hào)B的(2)(4)可知邊u2iv2i及v2iu2i+2(或v4k+2u2)的標(biāo)號(hào)有以下幾種情況:

(1)u2iv2i=|24k?12i+2?(12i+6)|=24k?24i+15,i=1,2,…,k;

(2)u2iv2i=|24k?12i+14?(12i?1)|=24i?24k?15,i=k+1,k+2,…,2k;

(3)u4k+2v4k+2=|12(2k+1)?1?0|=24k+11;

(4)v2iu2i+2=|24k?12(i+1)+21?(12i+6)]|=24i?24k+3,i=1,2,…,k?1;

(5)v2ku2k+1=|12(k+1)?1?(12k+6)|=5;

(6)v2iu2i+2=|24k?12i+14?[12(i+1)?1]|=24i?24k?3,i=k+1,k+2,…,2k;

(7)v4k+2u2=|12k?12+21?0|=24k+9;

首先,由(一)易知,在u1u2…u4k+2u1中,各邊的標(biāo)號(hào)均為奇數(shù),都是以24(或-24)為公差的等差數(shù)列,且范圍為:

(1)29≤u2i?1u2i≤24k+5,i=1,2,…,k;

(2)17≤u2iu2i+1≤24k?7,i=1,2,…,k;

(3)u2k+1u2k+2=7;

(4)23≤u2i?1u2i≤24k?1,i=k+2,k+3,…,2k+1;

(5)11≤u2iu2i+1≤24k?13,i=k+1,k+2,…,2k;

(6)u4k+2u1=24k+7;

由于首項(xiàng)(或末項(xiàng))各不相等而公差均為24(或-24),則依等差數(shù)列的性質(zhì)知,在u1u2…u4k+2u1中各邊的標(biāo)號(hào)不相等.

其次,由(二)易知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k+1u1)中,各邊的標(biāo)號(hào)也均為奇數(shù)且都是以24(或-24)為公差的等差數(shù)列,且范圍為:

(1)25≤u2i?1v2i?1≤24k+1,i=1,2,…,k;

(2)u2k+1v2k+1=3;

(3)19≤u2i?1u2i?1≤24k?5,i=k+2,k+3,…,2k+1;

(4)13≤v2i?1u2i+1≤24k?11,i=1,2,…,k;

(5)v2k+1u2k+3=1;

(6)31≤v2i?1u2i+1≤24k?17,i=k+2,k+3,…,2k;

(7)v4k+1u1=24k+3;

同樣,由于首項(xiàng) (或末項(xiàng))各不相等而公差均為 24(或 -24),則依等差數(shù)列的性質(zhì)知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k+1u1)中各邊的標(biāo)號(hào)不相等.

再次,由(三)易知,在邊u2iv2i及v2iu2i+2(或v4k+2u2)中,各邊的標(biāo)號(hào)也均為奇數(shù)且都是以24(或-24)為公差的等差數(shù)列,且范圍為:

(1)15≤u2iv2i≤24k?9,i=1,2,…,k;

(2)9≤u2iv2i≤24k?15,i=k+1,k+2,…,2k;

(3)u4k+2u4k+2=24k+11;

(4)27≤v2iu2i+2≤24k?21,i=1,2,…,k?1;

(5)v2ku2k+2=5;

(6)21≤v2iu2i+2≤24k?3,i=k+1,k+2,…,2k;

(7)v4k+2u2=24k+9;

同樣,由于首項(xiàng) (或末項(xiàng))各不相等而公差均為 24(或 -24),則依等差數(shù)列的性質(zhì)知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k+2u2)中各邊的標(biāo)號(hào)不相等.

最后,(一)、(二)和(三)中首項(xiàng)(或末項(xiàng))也各不相等而公差均為24(或-24),則依等差數(shù)列的性質(zhì)知,三類(lèi)邊的標(biāo)號(hào)范圍互不相等.

定理 2.1圖是奇優(yōu)美圖.

證明由引理 1、引理 2,可得,當(dāng) n=4k(k≥2)時(shí),圖存在奇優(yōu)美標(biāo)號(hào)A,所以圖是奇優(yōu)美圖.由引理3、引理4,可得,當(dāng)n=4k+2時(shí),圖存在奇優(yōu)美標(biāo)號(hào)B,所以圖是奇優(yōu)美圖.故圖是奇優(yōu)美圖.

(1)u2i?1=2i?2,i=1,2,…,2k;

(2)u2i=2i?1,i=1,2,…,k；u2i=2i+1,i=k+1,…,2k;

(3)v1=8k+1;v2i?1=16k+2i?1,i=2,…,k;v2i?1=16k+2i+1,i=k+1,…,2k;

(4)v2i=8k+2i+2,i=1,2,…,2k.

按照標(biāo)號(hào)C可得如下結(jié)果:

引理3.1圖中各頂點(diǎn)的標(biāo)號(hào)均不相同,即圖中的頂點(diǎn)集與集合{0,1,2,…,24k?1}構(gòu)成單射.

證明首先,由標(biāo)號(hào) C可得,圖各頂點(diǎn)的標(biāo)號(hào)大于等于零且小于等于 20k+1.其次,由 (1)、(2)得,頂點(diǎn) u1,u2,…,u4k中奇點(diǎn)的標(biāo)號(hào)均為偶數(shù),偶點(diǎn)的標(biāo)號(hào)均為奇數(shù),所以U={u1,u2,…,u4k}中各頂點(diǎn)的標(biāo)號(hào)均不相同；同樣,由(3)、(4)得,頂點(diǎn)v1,v2,…,v4k中奇點(diǎn)的標(biāo)號(hào)均為奇數(shù),偶點(diǎn)的標(biāo)號(hào)均為偶數(shù),所以V={v1,v2,…,v4k}中各頂點(diǎn)的標(biāo)號(hào)均不相同.另外,對(duì)于頂點(diǎn)u1,u2,…,u4k中的奇點(diǎn)與v1,v2,…,v4k中的偶點(diǎn),若存在i,j,使得u2i?1=v2j,即有

從而有

這與i,j=1,2,…,2k矛盾;而對(duì)于頂點(diǎn)u1,u2,…,u4k中的偶點(diǎn)與v1,v2,…,v4k中的奇點(diǎn),若存在i,j,使得u2i=v1或u2i=v2j?1,即有

從而有

這都與i,j相應(yīng)的取值范圍矛盾,由此U={u1,u2,…,u4k}中各頂點(diǎn)與V={v1,v2,…,v4k}中各頂點(diǎn)的標(biāo)號(hào)均不相同.

引理 3.2圖中各邊的標(biāo)號(hào)均不相同,即圖的邊集與集合{1,3,…,24k?1}構(gòu)成一一對(duì)應(yīng).

證明仿引理2.2,我們把邊的標(biāo)號(hào)分為三大類(lèi)來(lái)考慮.

(一)由標(biāo)號(hào)的(1)、(2)可知u1u2…u4ku1中邊的標(biāo)號(hào)有以下幾種情況:

(1)u2i?1u2i=2i?2+(2i?1)=4i?3,i=1,2,…,k;

(2)u2iu2i+1=2(i+1)?2+(2i?1)=4i?1,i=1,2,…,k;

(3)u2i?1u2i=2i?2+(2i+1)=4i?1,i=k+1,k+2,…,2k;

(4)u2iu2i+1=2(i+1)?2+(2i+1)=4i+1,i=k+1,k+2,…,2k?1;

(5)u4ku1=4k+1;

(二)由標(biāo)號(hào)C的(1)、(3)可知邊u2i?1v2i?1及v2i?1u2i+1(或v4k?1u1)的標(biāo)號(hào)有以下幾種情況:

(1)u1u1=8k+1;

(2)u2i?1v2i?1=2i?2+(16k+2i?1)=16k+4i?3,i=2,3,…,k;

(3)u2i?1v2i?1=2i?2+(16k+2i+1)=16k+4i?1,i=k+1,k+2,…,2k;

(4)v1u3=8k+3;

(5)v2i?1u2i+1=2(i+1)?2+(16k+2i?1)=16k+4i?1,i=2,3,…,k;

(6)v2i?1u2i+1=2(i+1)?2+(16k+2i+1)=16k+4i+1,i=k+1,k+2,…,2k?1;

(7)v4k?1u1=20k+1;

(三)由標(biāo)號(hào)C的(2)、(4)可知邊u2iv2i及v2iu2i+2(或v4ku2)的標(biāo)號(hào)有以下幾種情況:

(1)u2iv2i=2i?1+(8k+2i+2)=8k+4i+1,i=1,2,…,k;

(2)u2iv2i=2i+1+(8k+2i+2)=8k+4i+3,·i=k+1,k+2,…,2k;

(3)v2iu2i+2=2(i+1)?1+(8k+2i+2)=8k+4i+3,i=1,2,…,k?1;

(4)v2iu2i+2=2(i+1)+1+(8k+2i+2)=8k+4i+5,i=k,k+1,…,2k?1;

(5)v4ku2=12k+3.

首先,由(一)易知,在u1u2…u4ku1中,各邊的標(biāo)號(hào)均為奇數(shù),都是以4為公差的等差數(shù)列,且范圍為:

(1)1≤u2i?1u2i≤4k?3,i=1,2,…,k;

(2)3≤u2iu2i+1≤4k?1,i=1,2,…,k;

(3)4k+3≤u2i?1u2i≤8k?1,i=k+1,k+2,…,2k;

(4)4k+5≤u2iu2i+1≤8k?3,i=k+1,…,2k?1;

(5)u4ku1=4k+1;

由邊的標(biāo)號(hào)范圍及等差數(shù)列的性質(zhì)知,在u1u2…u4ku1中各邊的標(biāo)號(hào)不相等.

其次,由(二)易知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k?1u1)中,各邊的標(biāo)號(hào)也均為奇數(shù)且都是以4為公差的等差數(shù)列,且范圍為:

(1)u1v1=8k+1;

(2)16k+5≤u2i?1v2i?1≤20k?3,i=2,3,…,k;

(3)20k+3≤u2i?1v2i?1≤24k?1,i=k+1,k+2,…,2k;

(4)v1u3=8k+3;

(5)16k+7≤v2i?1u2i+1≤20k?1,i=2,3,…,k;

(6)20k+5≤v2i?1u2i+1≤24k?3,i=k+1,k+2,…,2k?1;

(7)v4k?1u1=20k+1;

同樣,由邊的標(biāo)號(hào)范圍及等差數(shù)列的性質(zhì)知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k?1u1)中各邊的標(biāo)號(hào)不相等.

再次,由(三)易知,在邊u2iv2i及 v2iu2i+2(或v4ku1)中,各邊的標(biāo)號(hào)也均為奇數(shù)且都是以4為公差的等差數(shù)列,且范圍為:

(1)8k+5≤u2iv2i≤12k+1,i=1,2,…,k;

(2)12k+7≤u2iu2i≤16k+3,i=k+1,k+2,…,2k;

(3)8k+7≤v2iu2i+2≤12k?1,i=1,2,…,k?1;

(4)12k+5≤v2iu2i+2≤16k+1,i=k,k+1,…,2k?1;

(5)v4ku2=12k+3.

同樣,由邊的標(biāo)號(hào)范圍及等差數(shù)列的性質(zhì)知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4ku2)中各邊的標(biāo)號(hào)不相等.由上可得,三類(lèi)邊的標(biāo)號(hào)范圍互不重疊,故也互不相等.綜上所述,圖中各邊的標(biāo)號(hào)均不相同,即圖的邊集與集合{1,3,5,…,24k?1}構(gòu)成一一對(duì)應(yīng).

定理 3.2當(dāng)n=4k(k≥2)時(shí),圖是奇強(qiáng)協(xié)調(diào)圖.

證明由引理3.1、引理3.2可得當(dāng)n=4k(k≥2)時(shí),圖存在奇強(qiáng)協(xié)調(diào)標(biāo)號(hào)C,所以圖是奇強(qiáng)協(xié)調(diào)圖.

4 注記

圖1 圖28的奇優(yōu)美標(biāo)號(hào)

圖2 圖210的奇優(yōu)美標(biāo)號(hào)

圖3 圖28的奇強(qiáng)協(xié)調(diào)標(biāo)號(hào)

圖4 圖216的奇強(qiáng)協(xié)調(diào)標(biāo)號(hào)

同時(shí)我們提出如下猜想:

[1]Ringel G.Problem 25 in theory of graph s and its application[J].Proc.Symposium Smolenice,1963(3):162-167.

[2]Frank Hsu D.Harmonious labelings of windmill graphs and related graphs[J].Journal of Graph Theory, 1982,6(1):85-87.

[3]Gallian A.A dynamic survey of graph labeling[J].The Electronic Journal of Combinatorics,2000,12:1-95.

[4]冉紅,李武裝.直徑為4的樹(shù)的奇強(qiáng)協(xié)調(diào)性[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2007,37(12):133-136.

[5]李武裝,苗宗文,嚴(yán)謙泰.幾類(lèi)有趣圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2011,41(4):234-240.

[6]劉廣軍,關(guān)于奇強(qiáng)協(xié)調(diào)圖的一些結(jié)果[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(11):271-275.

[7]林育青,鐘發(fā)勝,童細(xì)心,等.圖P3n的奇優(yōu)美標(biāo)號(hào)算法[J].數(shù)學(xué)理論與應(yīng)用,2013,33(4):29-34.

[8]林育青,張玲瑛,鐘發(fā)勝等.關(guān)于奇優(yōu)美圖及奇強(qiáng)協(xié)調(diào)圖的一點(diǎn)注記[J].貴州師范大學(xué)學(xué)報(bào),2014,32(2):43-46.

[9]張玲瑛,林育青,鐘發(fā)勝,等.關(guān)于圖2×Cn的標(biāo)號(hào)[J].北華大學(xué)學(xué)報(bào),2014,15(2):174-178.

[10]童細(xì)心,林育青,鐘發(fā)勝.圈Cn的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].南師范大學(xué)學(xué)報(bào),2014,39(8):10-13.

[11]林育青,童細(xì)心,張玲瑛.太陽(yáng)圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2015,45(18):271-280.

[12]Gnanajothi R B.Topics is Graph Theory[D].India:Madurai Kamaraj University,1991.

[13]Bandy J,Murty U S R.Graph Theory with Application[M].New York:The MaCmillan Press Ltd,1976.

Odd gracefulness and odd strongly harmoniousness of the graphs

Lin Yuqing
(Department of Nature,Shantou Polytechnic,Shantou 515041,China)

The paper de fi nesand analyzes odd-graceful and odd-strongly harmonious graphs.With the help of construction method,the graphsare respectively given when n=4k(k≥2)、n=4k+2 using Oddgraceful Algorithm and when n=4k(k≥2)using Odd-strongly harmonious Algorithm,and fi nally it concludes that graphis Odd-graceful graph when n=2k(k≥3)and are graphis Odd-strongly harmonious graph when n=4k(k≥2),which promotes the study of odd-graceful and odd-strongly harmonious attributes of the graph.The paper also proposes a conjecture thatis not a Odd-strongly harmonious graph when n=4k+2.

odd graceful graph,odd strongly harmonious graph,graphs

O157.5

A

1008-5513(2017)01-0001-11

10.3969/j.issn.1008-5513.2017.01.001

2016-12-22.

汕頭職業(yè)技術(shù)學(xué)院重點(diǎn)資助課題(SZK2013Z1).

林育青(1966-),副教授,研究方向:圖論.

2010 MSC:O5C17