童細心

（汕頭職業(yè)技術(shù)學院 自然科學系，廣東 汕頭 515041）

啞鈴圖2Cn+Pl的奇優(yōu)美性和奇強協(xié)調(diào)性

童細心

（汕頭職業(yè)技術(shù)學院 自然科學系，廣東 汕頭 515041）

研究了啞鈴圖2Cn+Pl的奇優(yōu)美性和奇強協(xié)調(diào)性，得到了啞鈴圖2Cn+Pl在n=4k以及n= 4k+2時是奇優(yōu)美圖，在n=4k時是奇強協(xié)調(diào)圖等結(jié)論.

啞鈴圖；奇優(yōu)美標號；奇優(yōu)美圖；奇強協(xié)調(diào)標號；奇強協(xié)調(diào)圖

圖論是數(shù)學的一個重要分支，而優(yōu)美圖是圖論的一個重要內(nèi)容.由于它應用的廣泛性，一直是人們研究的熱點，也取得了很多研究成果[1-13].1991年，Gnanajoethi提出一個猜想：“每棵樹都是奇優(yōu)美的”[3]，1982年，F(xiàn)ank Hsu D[4]引入圖的強協(xié)調(diào)標號.由于缺乏一個系統(tǒng)和有力的工具，迄今只能對一些特殊圖探索其奇優(yōu)美性和奇強協(xié)調(diào)性.本文研究了一類啞鈴圖的奇優(yōu)美性和奇強協(xié)調(diào)性，得到了如下結(jié)果：

定理1 當n=4k時，啞鈴圖2Cn+Pl是奇優(yōu)美圖．

定理2 當n=4k+2時，啞鈴圖2Cn+Pl是奇優(yōu)美圖.

定理3 當n=4k時，啞鈴圖2Cn+Pl是奇強協(xié)調(diào)圖.

定義1[3]對于一個簡單圖G=（V，E），V，E分別是G的頂點集和邊集.若對圖G的任意一個頂點v，存在一個整數(shù)（fv）（稱為頂點v的標號），當f是V到{0,1,2,…,2|E|-1}的一個單射，且導出的邊標號g(e)=|f(u)-f(v)|,e=uv滿足g是E到{1，3，5，…，2|E|-1}的一個一一對應，則稱圖G是奇優(yōu)美圖，稱f為圖G的奇優(yōu)美標號．

定義2[4]對于一個簡單圖G=（V，E），若存在一個映射：f∶V（G）→{0,1,2,…,2|E|-1}滿足：（1）f是單射；（2）?uv∈E(G )，令（fuv）=（fu）+（fv），有f是E（G）到{1,3,5,…,2|E|-1}的一個一一對應，則稱圖G是奇強協(xié)調(diào)圖，稱f為圖G的奇強協(xié)調(diào)標號．

定義3[14-15]用一條長為l-1的路連接兩個圈

Cn（u）=u1u2…unu1和Cm（v）=v1v2…vmv1的一對頂點ui，vj所得到的圖類稱為啞鈴圖，記為Cn+Cm+Pl.

在本文中，記連接兩個圈的頂點ui，vj分別為unv1（見圖1），且僅討論m=n的情形，此時啞鈴圖記為2Cn+Pl.為敘述方便，本文規(guī)定所討論的圖都是無向簡單圖，v既表示點v，也表示點v的標號.uv既表示邊，也表示該邊的標號.v2p點稱為偶點，v2p-1稱為奇點

圖1 啞鈴圖Cn+Cm+PlFig.1Dumbbell-shape graphs Cn+Cm+Pl

1 定理1與定理2的證明

情形1 當n=4k，l=2t時，啞鈴圖2Cn+Pl是奇優(yōu)美圖.

當n=4k，l=2t時，啞鈴圖2Cn+Pl的頂點數(shù)為2n+l-2=8k+2t-2，邊數(shù)為2n+l-1=8k+2t-1，此時2|| E-1=16k+4t-3.給出啞鈴圖的各頂點的標號遞推算法A如下：

（1）u2i-1=2i-2，i=1，2，…，2k.

（2）u2i=16k+4t-2i-1，i=1，2，…，2k-1；u4k=4k-1.

（3）c2i-1=12k+4t-2i-2，i=1，2，…，t-1；c2i=4k+2i-1，i=1，2，…，t-1.

（4）v2i-1=12k+2t-2i-4，i=1，2，…，k+1；v2i-1=12k+ 2t-2i+2，i=k+2，k+3，…，2k.

（5）v2i=4k+2t+2i-3，i=1，2，…，k；v2i=4k+2t+2i-1，i=k+1，k+2，…，2k.

按照算法A可得以下結(jié)果：

引理1 當n=4k，l=2t時，啞鈴圖2Cn+Pl的頂點集與集合{0，1，2，…，16k+4t-3}構(gòu)成單射.

證明 當n=4k，l=2t時，記M是啞鈴圖2Cn+Pl的所有頂點標號集合，由算法A的（1）-（5）易知：

由此易驗證，Mi∩Mj=?，i≠j且i，j=1，2，3，4，5.即當n=4k，l=2t時，啞鈴圖2Cn+Pl中各頂點的標號均不相同.又所有頂點標號的集合M=M1∪M2∪M3∪M4∪M5中最小數(shù)是0（在M1中），最大數(shù)是16k+4t-3（在M2中），即當n=4k，l=2t時，啞鈴圖2Cn+Pl的頂點集與集合{0，1，2，…，16k+4t-3}構(gòu)成單射．

引理2 當n=4k，l=2t時，啞鈴圖2Cn+Pl的邊集與集合{1，3，5，…，16k+4t-3}構(gòu)成一一對應．

證明 由算法A知，各頂點的標號最小為零，最大為16k+4t-3，故邊的標號均不超過16k+4t-3.把邊的標號分為三大類來考慮.

（一）由算法A的（1）（2）可知圈u1u2…u4ku1中邊的標號有以下幾種情況：

（二）由算法A的（2）（3）（4）可知路u4kc1c2…cl-2v1中邊的標號有以下幾種情況：

（三）由算法A的（4）（5）可知圈v1v2…v4kv1中邊的標號有以下幾種情況：

首先，由（一）易知，在圈u1u2…u4ku1中，各邊的標號均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）8k+4t+5≤u2i-1u2i≤16k+4t-3，i=1，2，…，2k-1；

（2）u4k-1u4k=1；

（3）8k+4t+3≤u2iu2i+1≤16k+4t-5，i=1，2，…，2k-1；

（4）u4ku1=4k-1；

由邊的標號范圍及等差數(shù)列的性質(zhì)知，在圈u1u2…u4ku1中各邊的標號不相等.

其次，由（二）易知，路u4kc1c2…cl-2v1中，各邊的標號均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）u4kc1=8k+4t+1；

（2）8k+7≤c2i-1c2i≤8k+4t-1，i=1，2，…，t-1；

（3）8k+9≤c2ic2i+1≤8k+4t-3，i=1，2，…，t-2；

（4）v2t-2v1=8k+5；

由邊的標號范圍及等差數(shù)列的性質(zhì)知，在路u4kc1c2…cl-2v1中各邊的標號不相等.

再次，由（三）易知，在圈v1v2…v4kv1中，各邊的標號也均為奇數(shù)且都是以4為公差的等差數(shù)列，且范圍為：

（1）4k+7≤v2i-1v2i≤8k+3，i=1，2，…，k；

（2）v2k+1v2k+2=4k+1；

（3）3≤v2i-1v2i≤4k-5，i=k+2，…，2k；

（4）4k+5≤v2iv2i+1≤8k+1，i=1，2，…，k；

（5）5≤v2iv2i+1≤4k-3，i=k+1，…，2k-1；

（6）v4kv1=4k+3.

同樣，由邊的標號范圍及等差數(shù)列的性質(zhì)知，在圈v1v2…v4kv1中，各邊的標號不相等.

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

綜上所述，當n=4k，l=2t時，啞鈴圖2Cn+Pl各邊的標號均不相同，且全為奇數(shù).即當n=4k，l=2t時，啞鈴圖2Cn+Pl的邊集與集合構(gòu)成一一對應．

由引理1、引理2及定義1知，情形1成立，即當n=4k，l=2t時，啞鈴圖2Cn+Pl是奇優(yōu)美圖.

情形2 當n=4k，l=2t+1時，啞鈴圖2Cn+Pl是奇優(yōu)美圖.

當n=4k，l=2t+1時，啞鈴圖2Cn+Pl的頂點數(shù)為2n+l-2=8k+2t-1，邊數(shù)為2n+l-1=8k+2t，此時2|| E-1=16k+2t-1.給出啞鈴圖2Cn+Pl的各頂點的標號遞推算法B如下：

（1）u2i-1=2i-2，i=1，2，…，2k．

（2）u2i=16k+4t-2i+1，i=1，2，…，2k-1；u4k=4k-1．

（3）c2i-1=12k+4t-2i+4，i=1，2，…，t；c2i=4k+2i-1，i= 1，2，…，t-1．

（4）v2i-1=4k+2t+2i-3，i=1，2，…，k+1，v2i-1=4k+2t+2i-1，i=k+2，k+3，…，2k.

（5）v2i=12k+2t-2i+4，i=1，2，…，k；v2i=12k+2t-2i+ 2，i=k+1，k+2，…，2k．

按照算法B可得以下結(jié)果：

引理3 當n=4k，l=2t+1時，啞鈴圖2Cn+Pl的頂點集與集合{0，1，2，…，16k+4t-1}構(gòu)成單射.

證明 仿引理1的證明即可.

引理4 當n=4k，l=2t+1時，啞鈴圖2Cn+Pl的邊集與集合{1，3，5，…，16k+4t-1}構(gòu)成一一對應．

證明 仿引理2的證明即可.

再由引理3、引理4及定義1知，情形2成立，即當n=4k，l=2t+1時，啞鈴圖2Cn+Pl是奇優(yōu)美圖.

定理1 當n=4k時，啞鈴圖2Cn+Pl是奇優(yōu)美圖．

證明 由情形1、情形2可知，定理1成立．

情形3 當n=4k+2，l=2t時，啞鈴圖2Cn+Pl是奇優(yōu)美圖．

當n=4k+2，l=2t時，啞鈴圖2Cn+Pl的頂點數(shù)為2n+l-2=8k+2t+2，邊數(shù)為2n+l-1=8k+2t+3，此時2||

E-1=16k+4t+5.此時給出啞鈴圖2Cn+Pl的各頂點的標號遞推算法如下：

（1）u2i-1=2i-2，i=1，2，…，2k+1．

（2）u2i=16k+4t-2i+7，i=1，2，…，2k；u4k+2=4k+1．

（3）c2i-1=12k+4t-2i+8，i=1，2，…，t-1；c2i=4k+2i+ 1，i=1，2，…，t-1．

（4）v2i-1=12k+2t-2i+10，i=1，2，…，k+1，v2i-1=12k+2t-2i+8，i=k+2，…，2k+1.

（5）v2i=4k+2t+2i-1，i=1，2，…，k+1；v2i=4k+2t+2i+ 1，i=k+2，k+3，…，2k+1．

按照算法C可得以下結(jié)果：

引理5 當n=4k+2，l=2t時，啞鈴圖2Cn+Pl的頂點集與集合{0，1，2，…，16k+4t+5}構(gòu)成單射.

證明 仿引理1的證明即可.

引理6 當n=4k+2，l=2t時，啞鈴圖2Cn+Pl的邊集與集合{1，3，5，…，16k+4t+5}構(gòu)成一一對應

證明 仿引理2的證明即可.

再由引理5、引理6及定義1知，情形3成立，即當n=4k+2，l=2t時，啞鈴圖2Cn+Pl是奇優(yōu)美圖.

情形4 當n=4k+2，l=2t+1時，啞鈴圖2Cn+Pl是奇優(yōu)美圖．

當n=4k+2，l=2t+1時，啞鈴圖2Cn+Pl的頂點數(shù)為2n+l-2=8k+2t+3，邊數(shù)為2n+l-1=8k+2t+4，此時2||

E-1=16k+4t+7.此時給出啞鈴圖2Cn+Pl的各頂點的標號遞推算法D如下：

（1）u2i-1=2i-2，i=1，2，…，2k+1．

（2）u2i=16k+4t-2i+9，i=1，2，…，2k；u4k+2=4k+1．

（3）c2i-1=12k+4t-2i+10，i=1，2，…，t；c2i=4k+2i+1，i=1，2，…，t-1.

（4）v2i-1=4k+2t+2i-1，i=1，2，…，k+1，v2i-1=4k+2t+2i+1，i=k+2，k+3，…，2k+1.

（5）v2i=12k+2t-2i+10，i=1，2，…，k+1；v2i=12k+2t-2i+8，i=k+2，…，2k+1．

按照算法D可得以下結(jié)果：

引理7 當n=4k+2，l=2t+1時，啞鈴圖2Cn+Pl的頂點集與集合{0，1，2，…，16k+4t+7}構(gòu)成單射．

證明 仿引理1的證明即可.

引理8 當n=4k+2，l=2t+1時，啞鈴圖2Cn+Pl的邊集與集合{1，3，5，…，16k+4t+7}構(gòu)成一一對應．

證明 仿引理2的證明即可.

再由引理7、引理8及定義1知，情形4成立，即當n=4k+2，l=2t+1時，啞鈴圖2Cn+Pl是奇優(yōu)美圖.

定理2 當n=4k+2時，啞鈴圖2Cn+Pl是奇優(yōu)美圖．

證明 由情形3、情形4可知，定理2成立．

2 定理3的證明

情形5 當n=4k，l=2t時，啞鈴圖2Cn+Pl是奇強協(xié)調(diào)圖．

當n=4k，l=2t時，啞鈴圖2Cn+Pl的頂點數(shù)為2n+l-2=8k+2t-2，邊數(shù)為2n+l-1=8k+2t-1，此時2|| E-1= 16k+4t-3.給出啞鈴圖2Cn+Pl的各頂點的標號遞推算法E如下：

（1）u2i-1=2i-2，i=1，2，…，2k．

（2）u2i=2i-1，i=1，2，…，k；u2i=2i+1，i=k+1，k+ 2，…，2k．

（3）c2i-1=4k+2i-2，i=1，2，…，t-1；c2i=4k+2i+1，i= 1，2，…，t-1.

（4）v2i-1=4k+2t+2i-4，i=1，2，…，2k.

（5）v2i=4k+2t+2i-1，i=1，2，…，k；v2i=4k+2t+2i+1，i=k+1，k+2，…，2k．

按照算法E可得以下結(jié)果：

引理9 當n=4k，l=2t時，啞鈴圖2Cn+Pl的頂點集與集合{0，1，2，…，16k+4t-3}構(gòu)成單射．

證明 仿引理1的證明，當n=4k，l=2t時，啞鈴圖2Cn+Pl中各頂點的標號均不相同.又頂點標號中的最小數(shù)是0（由算法的（1）知），最大數(shù)8k+2t+1是（由算法的（5）知），顯然小于16k+4t-3.所以，當n=4k，l= 2t時，啞鈴圖2Cn+Pl的頂點集與集合構(gòu)成單射．

引理10 當n=4k，l=2t時，啞鈴圖2Cn+Pl的邊集與集合{1，3，5，…，16k+4t-3}構(gòu)成一一對應．

證明 由算法E，也把邊的標號分為三大類來考慮：

（一）由算法E的（1）（2）可知圈u1u2…u4ku1中邊的標號有以下幾種情況：

（1）u2i-1u2i=（2i-2）+（2i-1）=4i-3，i=1，2，…，k；

（2）u2i-1u2i=（2i-2）+（2i+1）=4i-1，i=k+1，k+2，…，2k；

（3）u2iu2i+1=（2i-1）+[2（i+1）-2]=4i-1，i=1，2，…，k；

（4）u2iu2i+1=（2i+1）+[2（i+1）-2]=4i+1，i=k+1，k+ 2，…，2k-1；

（5）u4ku1=（2×1-2）+（2·2k+1）=4k+1.

（二）由算法E的（2）（3）（4）可知路u4kc1c2…cl-2v1中邊的標號有以下幾種情況：

（1）u4kc1=（2·2k+1）+（4k+2×1-2）=8k+1；

（2）c2i-1c2i=（4k+2i-2）+（4k+2i+1）=8k+4i-1，i=1，2，…，t-1；

（3）c2ic2i+1=[4k+2（i+1）-2]+（4k+2i+1）=8k+4i+1，i= 1，2，…，t-2；

（4）c2t-2v1=[4k+2（t-1）+1]+（4k+2t+2×1-4）=8k+4t-3.

（三）由算法E的（4）（5）可知圈v1v2…v4kv1中邊的標號有以下幾種情況：

（1）v2i-1v2i=（4k+2t+2i-4）+（4k+2t+2i-1）=8k+4t+4i-5，i=1，2，…，k；

（2）v2i-1v2i=（4k+2t+2i-4）+（4k+2t+2i+1）=8k+4t+4i-3，i=k+1，…，2k；

（3）v2iv2i+1=（4k+2t+2i-1）+[4k+2t+2（i+1）-4]=8k+4t+4i-3，i=1，2，…，k；

（4）v2iv2i+1=（4k+2t+2i+1）+[4k+2t+2（i+1）-4]=8k+4t+4i-1，i=k+1，…，2k-1；

（5）v4kv1=（4k+2t+2·2k+1）+（4k+2t+2×1-4）=12k+ 4t-1.

仿引理2的證明知：在圈u1u2…u4ku1中各邊的標號不相等，在路u4kc1c2…cl-2v1中各邊的標號也不相等，在圈v1v2…v4kv1中各邊的標號也不相等；且三類邊的標號范圍互不重疊，故也互不相等.故當n=4k，l=2t時，啞鈴圖2Cn+Pl各邊的標號均不相同，且全為奇數(shù).即當n=4k，l=2t時，啞鈴圖2Cn+Pl的邊集與集合{1，3，5，…，16k+4t+3}構(gòu)成一一對應.

由引理9、引理10及定義2知，情形5成立，即當n=4k，l=2t時，啞鈴圖2Cn+Pl是奇強協(xié)調(diào)圖.

情形6 當n=4k，l=2t+1時，啞鈴圖2Cn+Pl是奇強協(xié)調(diào)圖．

當n=4k，l=2t+1時，啞鈴圖2Cn+Pl的頂點數(shù)為2n+l-2=8k+2t-1，邊數(shù)為2n+l-1=8k+2t，此時2|| E-1=16k+4t-1.給出啞鈴圖2Cn+Pl的各頂點的標號遞推算法F如下：

（1）u2i-1=2i-2，i=1，2，…，2k．

（2）u2i=2i-1，i=1，2，…，k；u2i=2i+1，i=k+1，k+ 2，…，2k．

（3）c2i-1=4k+2i-2，i=1，2，…，t；c2i=4k+2i+1，i=1，2，…，t-1.

（4）v2i-1=4k+2t+2i-1，i=1，2，…，2k.

（5）v2i=4k+2t+2i-2，i=1，2，…，k；v2i=4k+2t+2i，i=k+1，k+2，…，2k．

按照算法可得以下結(jié)果：

引理11 當n=4k，l=2t+1時，啞鈴圖2Cn+Pl的頂點集與集合{0，1，2，…，16k+4t-1}構(gòu)成單射．

證明 仿引理1，引理9的證明.

引理12 當n=4k，l=2t+1時，啞鈴圖2Cn+Pl的邊集與集合{1，3，5，…，16k+4t-1}構(gòu)成一一對應．

證明 仿引理2，引理10的證明.

由引理11、引理12及定義2知，情形6成立，即當n=4k，l=2t+1時，啞鈴圖2Cn+Pl是奇強協(xié)調(diào)圖.

定理3 當n=4k時，啞鈴圖2Cn+Pl是奇強協(xié)調(diào)圖.

證明 由情形5、情形6及定義2可知，定理3成立．

[1]Ringel G.Problem 25,in:Theory of Graphs and Its Applica?tion[J].Proc Symposium Smolenice,1963,1263:162-167.

[2]Gallian J A.A Dynamic Survey of Graph Labeling[J].The Electronic Journal of Combinatorics,2009,16(6):1-219.

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

[4]Frank Hsu D.Harmonious Labelings of Windmill Graphs and Related Graphs[J].Journal of Graph Theory,1982,6(1): 85-87.

[7]林育青.一類圖的優(yōu)美性[J].云南師范大學學報:自然科學版,2004,24(4):15-19.

[8]林育青.Cn與1Cn的優(yōu)美標號[J].安徽大學學報:自然科學版,2007,32(2):13-16.

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

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

[11]張玲瑛,林育青,鐘發(fā)勝,等.關(guān)于圖2×Cn的標號[J].北華大學學報:自然科學版,2014,15(2):174-178.

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

[14]ALI M,ALI G,ALI U,et a1.On cycle related graphs with constant metric dimension[J].Open J Discrete Math,2012, 2(1):21-23.

[15]TANG Zikai,HUANG Guihua,JIANG Xiaojuan,et al. The Metric Dimension of Dumbbell-Shape Graph[J]. Journal of Natural Science of Hunan Normal University, 2013,36(6):7-10.

[16]Bandy J A,Murty U S R.Graph Theory with Application [M].American Elsevier Publishing Co Inc New York,1976.

責任編輯：畢和平

Odd Gracefulness and odd Strongly Harmoniousness of Dumbbell-shape Graphs

TONG Xixin
（Department of Natural sciences，Shantou Polytechnic，Shantou515041，China）

Odd Gracefulness and Odd Strongly Harmoniousness of dumbbell-shape graphs 2Cn+Plhave been studied.This paper has described that dumbbell-shape graphs 2Cn+Plare Odd Graceful graph whenn=4kandn=4k+2,and that dumbbellshape graphs 2Cn+Plare Odd Strongly Harmonious graph whenn=4k.

dumbbell-shape graph；odd graceful labeling；odd graceful graph；odd strongly harmonious labeling；odd strongly harmonious graph

O 157.5

：A

：1674-4942（2015）01-0015-05

2014-10-29

汕頭職業(yè)技術(shù)學院2014年院級科研課題（SZK2014Y24）