童細(xì)心，林育青

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

棒棒糖圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性

童細(xì)心，林育青

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

研究了棒棒糖圖Cn＋Pl的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性，得到了棒棒糖圖Cn＋Pl在n=4k，4k＋2時(shí)是奇優(yōu)美圖，在n=4k時(shí)是奇強(qiáng)協(xié)調(diào)圖等結(jié)論.

棒棒糖圖；奇優(yōu)美標(biāo)號(hào)；奇優(yōu)美圖；奇強(qiáng)協(xié)調(diào)標(biāo)號(hào)；奇強(qiáng)協(xié)調(diào)圖.

0 引言

優(yōu)美圖是圖論中一個(gè)十分有趣且重要的內(nèi)容，對(duì)優(yōu)美圖的研究始于1967年，由于其標(biāo)號(hào)問題的應(yīng)用十分廣泛，一直是人們研究的熱點(diǎn).1991年，Gnanajoethi提出一個(gè)猜想：“每棵樹都是奇優(yōu)美的”[1]；1982年，F(xiàn)ank Hsu D[2]引入了圖的強(qiáng)協(xié)調(diào)標(biāo)號(hào)，從而使圖的標(biāo)號(hào)研究更加豐富，目前已取得了很多研究成果[1-11].由于缺乏一個(gè)系統(tǒng)和有力的工具，迄今只能對(duì)一些特殊圖類探索其奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性.

定義1[1]：對(duì)于簡單圖G=（V，E），若?v∈V，存在單射（f（v）稱為頂點(diǎn)v的標(biāo)號(hào)），且導(dǎo)出的邊標(biāo)號(hào)滿足g是E到的一個(gè)一一對(duì)應(yīng)，則稱圖G是奇優(yōu)美圖，稱f為圖G的奇優(yōu)美標(biāo)號(hào).

定義2[2]：對(duì)于簡單圖G=（V，E），若?v∈V，存在單射，且導(dǎo)出的邊標(biāo)號(hào)g（e）=g（uv）=f（u）＋f（v）滿足g是E到的一個(gè)一一對(duì)應(yīng)，則稱圖G是奇強(qiáng)協(xié)調(diào)圖，稱f為圖G的奇強(qiáng)協(xié)調(diào)標(biāo)號(hào).

定義3[12]：從圈Cn上的一個(gè)頂點(diǎn)ui懸掛一條長為l的路Pl所得到的圖類，稱為棒棒糖圖，記為Cn＋Pl.如圖1所示，我們記圈Cn的頂點(diǎn)為ui，i=1，2，…，n.路Pl的頂點(diǎn)為vi，i=1，2，…，l.

圖1 棒棒糖圖Cn＋Pl

本文研究了棒棒糖圖Cn＋Pl的奇優(yōu)美性及其奇強(qiáng)協(xié)調(diào)性，得到了如下結(jié)果：

定理1：當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

定理2：當(dāng)n=4k＋2時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

定理3：當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl是奇強(qiáng)協(xié)調(diào)圖.

本文中所討論的圖均為無向簡單圖，v表示頂點(diǎn)v，uv表示以u(píng)，v為頂點(diǎn)的邊，f（v）表示點(diǎn)v的標(biāo)號(hào)，簡記為v=f（v）；同理，f（uv）表示邊uv的標(biāo)號(hào)，也簡記為uv=f（uv）.其他未加說明的定義和符號(hào)均來自文[13].

1 定理1的證明

我們分n=4k，l=2t－1和n=4k，l=2t兩種情況證明棒棒糖圖是奇優(yōu)美圖.

1.1 情形1

當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)數(shù)為n＋l=4k＋2t－1，邊數(shù)為n＋l=4k＋2t－1，此時(shí).給出棒棒糖圖Cn＋Pl的各頂點(diǎn)的標(biāo)號(hào)遞推算法A如下：

（1）v2i－1=2i－2，i=1，2，…，t；

（2）v2i=8k＋4t－2i－1，i=1，2，…，t－1；

（3）u2i－1=8k＋2t－2i＋1，i=1，2，…，2k；

（4）u2i=2t＋2i－2，i=1，2，…，k；u2i=2t＋2i，i=k＋1，k＋2，…，2k.

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

引理1：當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋4t－3}構(gòu)成單射.

證明：當(dāng)n=4k，l=2t－1時(shí)，記M是棒棒糖圖Cn＋Pl的所有頂點(diǎn)標(biāo)號(hào)集合，由算法A的（1）-（4）易知：

由此易驗(yàn)證，Mi∩Mj=φ，i≠j且i，j=1，2，3，4.即當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl中各頂點(diǎn)的標(biāo)號(hào)均不相同.又所有頂點(diǎn)標(biāo)號(hào)的集合M=M1∪M2∪M3∪M4中最小數(shù)是0（在M1中），最大數(shù)是8k＋4t－3（在M2中），即當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋4t－3}構(gòu)成單射.

引理2：當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，3，5，…，8k＋4t－3}構(gòu)成一一對(duì)應(yīng).

證明：由算法A知，各頂點(diǎn)的標(biāo)號(hào)最小為零，最大為8k＋4t－3，故邊的標(biāo)號(hào)均不超過8k＋4t－3.我們把邊的標(biāo)號(hào)分為兩大類來考慮.

（一）由算法A的（1）（2）（3）可知路v1v2…vlu1中邊的標(biāo)號(hào)有以下幾種情況：

（二）由算A法的（3）（4）可知圈u1u2…u4ku1中邊的標(biāo)號(hào)有以下幾種情況：

首先，由（一）易知，在路v1v2…vlu1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）8k＋5≤v2i－1v2i≤8k＋4t－3，其中i=1，2，…，t－1；

（2）8k＋3≤v2iv2i＋1≤8k＋4t－5，其中i=1，2，…，t－1；

（3）v2t－1u1=8k＋1.

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

其次，由（二）易知，在圈u1u2…u4ku1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）4k＋3≤u2i－1u2i≤8k－1，其中i=1，2，…，k；

（2）1≤u2i－1u2i≤4k－3，其中i=k＋1，k＋2，…，2k；

（3）4k＋1≤u2iu2i＋1≤8k－3，其中i=1，2，…，k；

（4）3≤u2iu2i＋1≤4k－5，其中i=k＋1，k＋2，…，2k－1；

（5）u4ku1=4k－1.

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

最后，由上易知，兩類邊的標(biāo)號(hào)范圍互不重疊，故也互不相等.

綜上所述，當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl各邊的標(biāo)號(hào)均不相同.即當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，3，5，…，8k＋4t－3}構(gòu)成一一對(duì)應(yīng).

由引理1、引理2及定義1知，情形1成立，即當(dāng)n=4k，l=2t－1時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

1.2 情形2

當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)數(shù)為n＋l=4k＋2t，邊數(shù)為n＋l=4k＋2t，此時(shí).給出棒棒糖圖Cn＋Pl的各頂點(diǎn)的標(biāo)號(hào)遞推算法B如下：

（1）v2i－1=2i－2，i=1，2，…，t；

（2）v2i=8k＋4t－2i＋1，i=1，2，…，t；

（3）u2i－1=2t＋2i－2，i=1，2，…，2k；

（4）u2i=8k＋2t－2i＋1，i=1，2，…，k；u2i=8k＋2t－2i－1，i=k＋1，k＋2，…，2k.

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

引理3：當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋4t－1}構(gòu)成單射.

證明：當(dāng)n=4k，l=2t時(shí)，記N是棒棒糖圖Cn＋Pl的所有頂點(diǎn)標(biāo)號(hào)集合，由算法B的（1）-（4）易知：

由此易驗(yàn)證，Ni∩Nj=φ，i≠j且i，j=1，2，3，4.即當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl中各頂點(diǎn)的標(biāo)號(hào)均不相同.又所有頂點(diǎn)標(biāo)號(hào)的集合N=N1∪N2∪N3∪N4中最小數(shù)是0（在N1中），最大數(shù)是8k＋4t－1（在N2中）.即當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋4t－1}構(gòu)成單射.

引理4：當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，2，3，…，4k＋2t}構(gòu)成一一對(duì)應(yīng).

證明：由算法B知，各頂點(diǎn)的標(biāo)號(hào)最小為零，最大為8k＋4t－1，故邊的標(biāo)號(hào)均不超過8k＋4t－1.我們把邊的標(biāo)號(hào)分為兩大類來考慮.

（一）由算法B的（1）（2）（3）可知路v1v2…vlu1中邊的標(biāo)號(hào)有以下幾種情況：

（二）由算法B的（3）（4）可知圈u1u2…u4ku1中邊的標(biāo)號(hào)有以下幾種情況：

首先，由（一）易知，在路v1v2…vlu1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）8k＋3≤v2i－1v2i≤8k＋4t－1，其中i=1，2，…，t；

（2）8k＋5≤v2iv2i＋1≤8k＋4t－3，其中i=1，2，…，t－1；

（3）v2tu1=8k＋1.

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

其次，由（二）易知，在圈u1u2…u4ku1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）4k＋3≤u2i－1u2i≤8k－1，其中i=1，2，…，k；

（2）1≤u2i－1u2i≤4k－3，其中i=k＋1，k＋2，…，2k；

（3）4k＋1≤u2iu2i＋1≤8k－3，其中i=1，2，…，k；

（4）3≤u2iu2i＋1≤4k－5，其中i=k＋1，k＋2，…，2k－1；

（5）u4ku1=4k－1.

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

最后，由上易知，兩類邊的標(biāo)號(hào)范圍互不重疊，故也互不相等.

綜上所述，當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl各邊的標(biāo)號(hào)均不相同.即當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，3，5，…，8k＋4t－1}構(gòu)成一一對(duì)應(yīng).

由引理3、引理4及定義1知，情形2成立，即當(dāng)n=4k，l=2t時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

定理1：當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

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

2 定理2的證明

同樣分n=4k＋2，l=2t－1和n=4k＋2，l=2t兩種情況證明棒棒糖圖是奇優(yōu)美圖.

2.1 情形3

當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)數(shù)為n＋l=4k＋2t＋1，邊數(shù)為n＋l=4k＋2t＋1，此時(shí).給出棒棒糖圖Cn＋Pl的各頂點(diǎn)的標(biāo)號(hào)遞推算法C如下：

（1）v2i－1=2i－2，i=1，2，…，t；

（2）v2i=8k＋4t－2i＋3，i=1，2，…，t－1；

（3）u2i－1=8k＋2t－2i＋5，i=1，2，…，k＋1；u2i－1=8k＋2t－2i＋3，i=k＋2，k＋3，…，2k＋1；

（4）u2i=2t＋2i－2，i=1，2，…，2k；u4k＋2=4k＋2t＋2．

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

引理5：當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋4t＋1}構(gòu)成單射.

證明當(dāng)n=4k＋2，l=2t－1時(shí)，記P是棒棒糖圖Cn＋Pl的所有頂點(diǎn)標(biāo)號(hào)集合，由算法C的（1）-（4）易知：

由此易驗(yàn)證，Pi∩Pj=φ，i≠j且i，j=1，2，3，4.即當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl中各頂點(diǎn)的標(biāo)號(hào)均不相同.又所有頂點(diǎn)標(biāo)號(hào)的集合P=P1∪P2∪P3∪P4中最小數(shù)是0（在P1中），最大數(shù)是8k＋4t＋1（在P2中），即當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋4t＋1}構(gòu)成單射.

引理6：當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，3，5，…，8k＋4t＋1}構(gòu)成一一對(duì)應(yīng).

證明：由算法C知，各頂點(diǎn)的標(biāo)號(hào)最小為零，最大為8k＋4t＋1，故邊的標(biāo)號(hào)均不超過8k＋4t＋1.我們可把邊的標(biāo)號(hào)分為兩大類來考慮.

（一）由算法C的（1）（2）（3）可知路v1v2…vlu1中邊的標(biāo)號(hào)有以下幾種情況：

（二）由算法C的（3）（4）可知圈u1u2…u4k＋2u1中邊的標(biāo)號(hào)有以下幾種情況：

首先，由（一）易知，在路v1v2…vlu1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）8k＋9≤v2i－1v2i≤8k＋4t＋1，其中i=1，2，…，t－1；

（2）8k＋7≤v2iv2i＋1≤8k＋4t－1，其中i=1，2，…，t－1；

（3）v2t－1u1=8k＋5.

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

其次，由（二）易知，在圈u1u2…u4k＋2u1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）4k＋3≤u2i－1u2i≤8k＋3，其中i=1，2，…，k＋1；

（2）5≤u2i－1u2i≤4k－3，其中i=k＋2，k＋3，…，2k；

（3）u4k＋1u4k＋2=1；

（4）4k＋5≤u2iu2i＋1≤8k＋1，其中i=1，2，…，k；

（5）3≤u2iu2i＋1≤4k－1，其中i=k＋1，k＋2，…，2k；

（6）u4k＋2u1=4k＋1.

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

最后，由上易知，兩類邊的標(biāo)號(hào)范圍互不重疊，故也互不相等.

綜上所述，當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl各邊的標(biāo)號(hào)均不相同.即當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，3，5，…，8k＋4t＋1}構(gòu)成一一對(duì)應(yīng).

由引理5、引理6及定義1知，情形3成立，即當(dāng)n=4k＋2，l=2t－1時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

2.2 情形4

當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)數(shù)為n＋l=4k＋2t＋2，邊數(shù)為n＋l=4k＋2t＋2，此時(shí).此時(shí)給出棒棒糖圖Cn＋Pl的各頂點(diǎn)的標(biāo)號(hào)遞推算法D如下：

（1）v2i－1=2i－2，i=1，2，…，t；

（2）v2i=8k＋4t－2i＋5，i=1，2，…，t；

（3）u2i－1=2t＋2i－2，i=1，2，…，k＋1；u2i－1=2t＋2i，i=k＋2，k＋3，…，2k＋1；

（4）u2i=8k＋2t－2i＋5，i=1，2，…，2k；u4k＋2=4k＋2t＋1.

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

引理7：當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋4t＋3}構(gòu)成單射.

證明：當(dāng)n=4k＋2，l=2t時(shí)，記Q是棒棒糖圖Cn＋Pl的所有頂點(diǎn)標(biāo)號(hào)集合，由算法D的（1）-（4）易知：

易驗(yàn)證，Qi∩Qj=φ，i≠j且i，j=1，2，3，4.即當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl中各頂點(diǎn)的標(biāo)號(hào)均不相同.又所有頂點(diǎn)標(biāo)號(hào)的集合Q=Q1∪Q2∪Q3∪Q4中最小數(shù)是0（在Q1中），最大數(shù)是8k＋4t＋3（在Q2中），即當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋4t＋3}構(gòu)成單射.

引理8：當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，3，5，…，8k＋4t＋3}構(gòu)成一一對(duì)應(yīng).

證明：由算法D知，各頂點(diǎn)的標(biāo)號(hào)最小為零，最大為8k＋4t＋3，故邊的標(biāo)號(hào)均不超過8k＋4t＋3.我們可把邊的標(biāo)號(hào)分為兩大類來考慮.

（一）由算法D的（1）（2）（3）可知路v1v2…vlu1中邊的標(biāo)號(hào)有以下幾種情況：

（二）由算法C的（3）（4）可知圈u1u2…u4k＋2u1中邊的標(biāo)號(hào)有以下幾種情況：

首先，由（一）易知，在路v1v2…vlu1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）8k＋7≤v2i－1v2i≤8k＋4t＋3，其中i=1，2，…，t；

（2）8k＋9≤v2iv2i＋1≤8k＋4t＋1，其中i=1，2，…，t－1；

（3）v2tu1=8k＋5.

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

其次，由（二）易知，在圈u1u2…u4k＋2u1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）4k＋3≤u2i－1u2i≤8k＋3，其中i=1，2，…，k＋1；

（2）5≤u2i－1u2i≤4k－3，其中i=k＋2，k＋3，…，2k；

（3）u4k＋1u4k＋2=1；

（4）4k＋5≤u2iu2i＋1≤8k＋1，其中i=1，2，…，k；

（5）3≤u2iu2i＋1≤4k－1，其中i=k＋1，k＋2，…，2k；

（6）u4k＋2u1=4k＋1.

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

最后，由上易知，兩類邊的標(biāo)號(hào)范圍互不重疊，故也互不相等.

綜上所述，當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl各邊的標(biāo)號(hào)均不相同.即當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，3，5，…，8k＋4t＋3}構(gòu)成一一對(duì)應(yīng).

由引理7、引理8及定義1知，情形4成立，即當(dāng)n=4k＋2，l=2t時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

定理2：當(dāng)n=4k＋2時(shí)，棒棒糖圖Cn＋Pl是奇優(yōu)美圖.

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

3 定理3的證明

當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)數(shù)為n＋l=4k＋l，邊數(shù)為n＋l=4k＋l，此時(shí).給出棒棒糖圖Cn＋Pl的各頂點(diǎn)的標(biāo)號(hào)遞推算法E如下：

（1）vi=i－1，i=1，2，…，l；

（2）u2i－1=l＋2i－2，i=1，2，…，2k；

（3）u2i=l＋2i－1，i=1，2，…，k；u2i=l＋2i＋1，i=k＋1，k＋2，…，2k.

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

引理9：當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋2l－1}構(gòu)成單射.

證明：當(dāng)n=4k時(shí)，記R是棒棒糖圖Cn＋Pl的頂點(diǎn)標(biāo)號(hào)集合，由算法E的（1）-（3）易知：

易驗(yàn)證，Ri∩Rj=φ，i≠j且i，j=1，2，3.即當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl中各頂點(diǎn)的標(biāo)號(hào)均不相同.又所有頂點(diǎn)標(biāo)號(hào)的集合R=R1∪R2∪R3中最小數(shù)是0（在R1中），最大數(shù)是l＋4k＋1（在R3中，且顯然小于8k＋2l－1）.所以，當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl的頂點(diǎn)集與集合{0，1，2，…，8k＋2l－1}構(gòu)成單射.

引理10：當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl的邊集與集合{1，3，5，…，8k＋2l－1}構(gòu)成一一對(duì)應(yīng).

證明：由算法E知，我們把邊的標(biāo)號(hào)分為兩大類來考慮.

（一）由算法E的（1）（2）可知路v1v2…vlu1中邊的標(biāo)號(hào)有以下幾種情況：

（1）vivi＋1=（i＋l）＋[（i＋1）－1]=2i－1，其中i=1，2，…，l－1；

（2）vlu1=（l－1）＋（l＋2×1－2）=2l－1.

（二）由算法E的（2）（3）可知圈u1u2…u4ku1中邊的標(biāo)號(hào)有以下幾種情況：

（1）u2i－1u2i=（l＋2i－2）＋（l＋2i－1）=2l＋4i－3，其中i=1，2，…，k；

（2）u2i－1u2i=（l＋2i－2）＋（l＋2i＋1）=2l＋4i－1，其中i=k＋1，k＋2，…，2k；

（3）u2iu2i＋1=（l＋2i－1）＋[l＋2（i＋1）－2]=2l＋4i－1，其中i=1，2，…，k；

（4）u2iu2i＋1=（l＋2i＋1）＋[l＋2（i＋1）－2]=2l＋4i＋1，其中i=k＋1，k＋2，…，2k－1；

（5）u4ku1=（l＋2·2k＋1）＋（l＋2×1－2）=2l＋4k＋1.

首先，由（一）易知，在路v1v2…vlu1中，各邊的標(biāo)號(hào)均為奇數(shù)，且范圍為：

其次，由（二）易知，圈u1u2…u4ku1中，各邊的標(biāo)號(hào)均為奇數(shù)，都是以4為公差的等差數(shù)列，且范圍為：

（1）2l＋1≤u2i－1u2i≤2l＋4k－3，其中i=1，2，…，k；

（2）2l＋4k＋3≤u2i－1u2i≤2l＋8k－1，其中i=k＋1，k＋2，…，2k；

（3）2l＋3≤u2iu2i＋1≤2l＋4k－1，其中i=1，2，…，k；

（4）2l＋4k＋5≤u2iu2i＋1≤2l＋8k－3，其中i=k＋1，k＋2，…，2k－1；

（5）u4ku1=2l＋4k＋1.

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

最后，由上易知，兩類邊的標(biāo)號(hào)范圍互不重疊，故也互不相等.

綜上所述，當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl各邊的標(biāo)號(hào)均不相同，且全為奇數(shù).即當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl邊集與集合{1，3，5，…，8k＋2l－1}構(gòu)成一一對(duì)應(yīng).

定理3：當(dāng)n=4k時(shí)，棒棒糖圖Cn＋Pl是奇強(qiáng)協(xié)調(diào)圖.

證明：由引理9、引理10及定義2知，定理3成立.

[1]GNANAJOETHI R B.Topics is graph theory[D].India：Madurai Kamaraj University，1991.

[2]HSU D F.Harmonious labelings of windmill graphs and related graphs[J].Journal of Graph Theory.1982，6（1）：85-87.

[3]RINGEL G.Problem 25，theory of graphs and its application[J].Proc Symposium Smolenice，1963：162-167.

[4]GALLIAN J A.A dynamic survey of graph labeling[J].The Electronic Journal of Combinatorics，2009，16（6）：1-219.

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

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

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

[8]童細(xì)心.一類啞鈴圖的優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].汕頭大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，30（2）：38-43.

[9]童細(xì)心.啞鈴圖2Cn+Pl的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].海南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，28（1）：15-19.

[10]童細(xì)心.一類啞鈴圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性[J].貴州師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，33（3）：54-58.

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

[12]陳暑波，夏方禮，龍韜，等.棒棒糖圖的Merrifield-Simmons和Hosoya指數(shù)[J].湖南城市學(xué)院學(xué)報(bào)（自然科學(xué)版），2008，17（3）：39-41.

[13]BANDY J A，MURTY U S R.Graph theory with application[M].NewYork：American Elsevier Publishing Co Inc，1976.

Odd Gracefulness and Odd Strong Harmoniousness of Lollipop Graphs

TONG Xixin,LIN Yuqing
（Department of Natural Sciences,Shantou Polytechnic,Shantou 515041,Guangdong,China）

Odd gracefulness and odd strong harmoniousness of lollipop graphs Cn＋Plhave been studied.It is shown that lollipop graphs Cn＋Plare odd graceful graph when n=4k,4k＋2,and that lollipop graphs Cn＋Plare odd strongly harmonious graph when n=4k.

lollipop graphs;odd graceful labeling;odd graceful graph;odd strongly harmonious labeling;odd strongly harmonious graph.

O157.5

A

1001-4217（2017）02-0043-10

2016-01-05

童細(xì)心（1979—），男（漢族），湖南岳陽人，講師.研究方向：圖論.郵箱：txx2486@126.com.

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