圖2n的奇優美及其奇強協調性

林育青

(汕頭職業技術學院自然科學系,廣東 汕頭 515041)

林育青

(汕頭職業技術學院自然科學系,廣東 汕頭 515041)

該文定義了圖并研究了該圖的奇優美和奇強協調性.利用構造法分別給出了圖在n=4k(k≥2)、n=4k+2時的奇優美算法,在n=4k(k≥2)時,的奇強協調算法,進而證明了圖在n=2k(k≥3)時是奇優美圖,在n=4k(k≥2)時是奇強協調圖等結論,從而推動了對圖的奇優美性和奇強協調性的研究.最后提出猜想:當n=4k+2時,圖不是奇強協調圖.

奇優美圖;奇強協調圖;圖

1 引言

優美圖的提出始于1963年文獻[1]的一個猜想,由于它的趣味性和廣泛的應用性,一直以來深受人們的重視.1982年,文獻 [2]引入圖的強協調標號,1994年,Gnanajoethi提出猜想:“每棵樹都是奇優美的”[3]．推動了對圖的奇優美性和奇強協調性的研究,目前已有很多這方面的結果[4-11],但由于缺乏一個系統和有力的工具,迄今,只能對一些特殊圖類探索其奇優美性和奇強協調性.

定理 1.1當n=2k(k≥3)時,圖是奇優美圖.

定理 1.2當n=4k(k≥2)時,圖是奇強協調圖.

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

定義 1.2[12]一個簡單圖 G=(V,E)稱為奇優美的,如果存在一個單射,f:V(G)→{0,1,2,…,2|E|?1}對所有邊 uv=e∈E(G),由 f?(uv)=|f(u)?f(v)|導出的映射,有：f?:V(G)→{1,3,…,2|E|?1}是一個一一對應,f稱為G的奇優美標號.

定義 1.3[2]一個簡單圖 G=(V,E)稱為奇強協調的,如果存在一個單射f:V(G)→{0,1,2,…,2|E|?1},對所有邊 uv=e∈E(G),由 f?(uv)=f(u)+f(v)導出的映射,有：f?:V(G)→{1,3,…,2|E|?1}是一個一一對應,f稱為G的奇強協調標號.

為敘述方便,本文規定所討論的圖都是無向簡單圖,為敘述方便,v表示點 v,uv表示邊,f(v)表示點v的標號,簡單的記為v=f(v);同理,f(uv)表示邊uv的標號,也簡單的記為uv=f(uv)．

點v2p稱為偶點,v2p?1稱為奇點．其他未加說明的定義和符號均來自文獻[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.

按照標號A可得如下結果:

引理 2.1圖中各頂點的標號均不相同,即圖的頂點集與集合{0,1,2,…,24k?1}構成單射.

證明首先,由標號A可得,圖的頂點集中各頂點的標號大于等于零,小于等于24k?1.其次,由(1)、(2)得,頂點u1,u2,…,u4k中奇點的標號均為偶數,偶點的標號均為奇數,所以U={u1,u2,…,u4k}中各頂點的標號均不相同;由(3)、(4)得,頂點v1,v2,…,v4k中奇點的標號均為奇數,偶點的標號均為偶數,所以V={v1,v2,…,v4k}中各頂點的標號均不相同.另外,對于頂點U={u1,u2,…,u4k}中的奇點與V={v1,v2,…,v4k}中的偶點,若存在i,j,使得u2i?1=v2j,即2i?2=8k+2j+2,從而有i?j=4k+2,與i,j=1,2,…,2k矛盾;對于頂點U={u1,u2,…,u4k}中的偶點與V={v1,v2,…,v4k}中的奇點,若存在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相應的取值范圍矛盾,由此U={u1,u2,…,u4k}中各頂點與V={v1,v2,…,v4k}中各頂點的標號均不相同.

引理 2.2圖中各邊的標號均不相同.即圖的邊集與集合{1,3,…,24k?1}構成一一對應.

證明我們把邊的標號分為三大類來考慮.

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

(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;

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

(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;

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

(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中,各邊的標號均為奇數,都是以4為公差的等差數列,且范圍為:

(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;

由邊的標號范圍及等差數列的性質知,在u1u2…u4ku1中各邊的標號不相等.

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

(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;

同樣,由邊的標號范圍及等差數列的性質知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k?1u1)中各邊的標號不相等.

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

(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.

同樣,由邊的標號范圍及等差數列的性質知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4ku2)中各邊的標號不相等.

由上知,三類邊的標號范圍互不重疊,故也互不相等.

(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.

按照標號B可得如下結果：

引理 2.3圖中各頂點的標號均不相同,即圖的頂點集與集合{0,1,2,…,24k+11}構成單射.

證明首先,由標號B可得,圖的頂點集中各頂點的標號大于等于零,小于等于24k+11.其次,由(1)(2)得,頂點u1,u2,…,u4k+2中奇點的標號均為偶數,偶點的標號均為奇數,所以U={u1,u2,…,u4k+2}中各頂點的標號均不相同;由(3)(4)得,頂點v1,v2,…,v4k+2中奇點的標號均為奇數,偶點的標號均為偶數,所以V={v1,v2,…,v4k+2}中各頂點的標號均不相同.另外,對于頂點U={u1,u2,…,u4k+2}中的奇點與V={v1,v2,…,v4k+2}中的偶點,若存在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,這都與奇偶性質或i的取值范圍矛盾;對于頂點U={u1,u2,…,u4k}中的偶點與V={v1,v2,…,v4k}中的奇點,若存在i,j,u2i=v2j?1或u2i=v2k+1,即有

或

或

從而有

或

或

這都與i,j相應的取值范圍或奇偶性質矛盾,由此U={u1,u2,…,u4k+2}中各頂點與V= {v1,v2,…,v4k+2}中各頂點的標號均不相同.綜上所述,圖中各頂點的標號均不相同,即圖的頂點集與集合{0,1,2,…,24k+11}構成單射.

引理2.4圖中各邊的標號均不相同.即圖的邊集與集合{1,3,…,24k+ 11}構成一一對應.

證明我們把邊的標號分為三大類來考慮.

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

(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;

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

(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;

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

(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中,各邊的標號均為奇數,都是以24(或-24)為公差的等差數列,且范圍為:

(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;

由于首項(或末項)各不相等而公差均為24(或-24),則依等差數列的性質知,在u1u2…u4k+2u1中各邊的標號不相等.

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

(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;

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

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

(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;

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

最后,(一)、(二)和(三)中首項(或末項)也各不相等而公差均為24(或-24),則依等差數列的性質知,三類邊的標號范圍互不相等.

定理 2.1圖是奇優美圖.

證明由引理 1、引理 2,可得,當 n=4k(k≥2)時,圖存在奇優美標號A,所以圖是奇優美圖.由引理3、引理4,可得,當n=4k+2時,圖存在奇優美標號B,所以圖是奇優美圖.故圖是奇優美圖.

(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.

按照標號C可得如下結果:

引理3.1圖中各頂點的標號均不相同,即圖中的頂點集與集合{0,1,2,…,24k?1}構成單射.

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

從而有

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

從而有

這都與i,j相應的取值范圍矛盾,由此U={u1,u2,…,u4k}中各頂點與V={v1,v2,…,v4k}中各頂點的標號均不相同.

引理 3.2圖中各邊的標號均不相同,即圖的邊集與集合{1,3,…,24k?1}構成一一對應.

證明仿引理2.2,我們把邊的標號分為三大類來考慮.

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

(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;

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

(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;

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

(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中,各邊的標號均為奇數,都是以4為公差的等差數列,且范圍為:

(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;

由邊的標號范圍及等差數列的性質知,在u1u2…u4ku1中各邊的標號不相等.

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

(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;

同樣,由邊的標號范圍及等差數列的性質知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4k?1u1)中各邊的標號不相等.

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

(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.

同樣,由邊的標號范圍及等差數列的性質知,在邊u2i?1v2i?1及v2i?1u2i+1(或v4ku2)中各邊的標號不相等.由上可得,三類邊的標號范圍互不重疊,故也互不相等.綜上所述,圖中各邊的標號均不相同,即圖的邊集與集合{1,3,5,…,24k?1}構成一一對應.

定理 3.2當n=4k(k≥2)時,圖是奇強協調圖.

證明由引理3.1、引理3.2可得當n=4k(k≥2)時,圖存在奇強協調標號C,所以圖是奇強協調圖.

4 注記

圖1 圖28的奇優美標號

圖2 圖210的奇優美標號

圖3 圖28的奇強協調標號

圖4 圖216的奇強協調標號

同時我們提出如下猜想:

[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的樹的奇強協調性[J].數學的實踐與認識,2007,37(12):133-136.

[5]李武裝,苗宗文,嚴謙泰.幾類有趣圖的奇優美性和奇強協調性[J].數學的實踐與認識,2011,41(4):234-240.

[6]劉廣軍,關于奇強協調圖的一些結果[J].數學的實踐與認識,2013,43(11):271-275.

[7]林育青,鐘發勝,童細心,等.圖P3n的奇優美標號算法[J].數學理論與應用,2013,33(4):29-34.

[8]林育青,張玲瑛,鐘發勝等.關于奇優美圖及奇強協調圖的一點注記[J].貴州師范大學學報,2014,32(2):43-46.

[9]張玲瑛,林育青,鐘發勝,等.關于圖2×Cn的標號[J].北華大學學報,2014,15(2):174-178.

[10]童細心,林育青,鐘發勝.圈Cn的奇優美性和奇強協調性[J].南師范大學學報,2014,39(8):10-13.

[11]林育青,童細心,張玲瑛.太陽圖的奇優美性和奇強協調性[J].數學的實踐與認識,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.

汕頭職業技術學院重點資助課題(SZK2013Z1).

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

2010 MSC:O5C17