童细心

（汕头职业技术学院 自然科学系，广东 汕头 515041）

哑铃图2Cn+Pl的奇优美性和奇强协调性

童细心

（汕头职业技术学院 自然科学系，广东 汕头 515041）

研究了哑铃图2Cn+Pl的奇优美性和奇强协调性，得到了哑铃图2Cn+Pl在n=4k以及n= 4k+2时是奇优美图，在n=4k时是奇强协调图等结论.

哑铃图；奇优美标号；奇优美图；奇强协调标号；奇强协调图

图论是数学的一个重要分支，而优美图是图论的一个重要内容.由于它应用的广泛性，一直是人们研究的热点，也取得了很多研究成果[1-13].1991年，Gnanajoethi提出一个猜想：“每棵树都是奇优美的”[3]，1982年，Fank Hsu D[4]引入图的强协调标号.由于缺乏一个系统和有力的工具，迄今只能对一些特殊图探索其奇优美性和奇强协调性.本文研究了一类哑铃图的奇优美性和奇强协调性，得到了如下结果：

定理1 当n=4k时，哑铃图2Cn+Pl是奇优美图．

定理2 当n=4k+2时，哑铃图2Cn+Pl是奇优美图.

定理3 当n=4k时，哑铃图2Cn+Pl是奇强协调图.

定义1[3]对于一个简单图G=（V，E），V，E分别是G的顶点集和边集.若对图G的任意一个顶点v，存在一个整数（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是奇优美图，称f为图G的奇优美标号．

定义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是奇强协调图，称f为图G的奇强协调标号．

定义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.为叙述方便，本文规定所讨论的图都是无向简单图，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是奇优美图.

当n=4k，l=2t时，哑铃图2Cn+Pl的顶点数为2n+l-2=8k+2t-2，边数为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可得以下结果：

引理1 当n=4k，l=2t时，哑铃图2Cn+Pl的顶点集与集合{0，1，2，…，16k+4t-3}构成单射.

证明 当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中最小数是0（在M1中），最大数是16k+4t-3（在M2中），即当n=4k，l=2t时，哑铃图2Cn+Pl的顶点集与集合{0，1，2，…，16k+4t-3}构成单射．

引理2 当n=4k，l=2t时，哑铃图2Cn+Pl的边集与集合{1，3，5，…，16k+4t-3}构成一一对应．

证明 由算法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中，各边的标号均为奇数，都是以4为公差的等差数列，且范围为：

（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；

由边的标号范围及等差数列的性质知，在圈u1u2…u4ku1中各边的标号不相等.

其次，由（二）易知，路u4kc1c2…cl-2v1中，各边的标号均为奇数，都是以4为公差的等差数列，且范围为：

（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；

由边的标号范围及等差数列的性质知，在路u4kc1c2…cl-2v1中各边的标号不相等.

再次，由（三）易知，在圈v1v2…v4kv1中，各边的标号也均为奇数且都是以4为公差的等差数列，且范围为：

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

同样，由边的标号范围及等差数列的性质知，在圈v1v2…v4kv1中，各边的标号不相等.

最后，由上易知，三类边的标号范围互不重叠，故也互不相等.

综上所述，当n=4k，l=2t时，哑铃图2Cn+Pl各边的标号均不相同，且全为奇数.即当n=4k，l=2t时，哑铃图2Cn+Pl的边集与集合构成一一对应．

由引理1、引理2及定义1知，情形1成立，即当n=4k，l=2t时，哑铃图2Cn+Pl是奇优美图.

情形2 当n=4k，l=2t+1时，哑铃图2Cn+Pl是奇优美图.

当n=4k，l=2t+1时，哑铃图2Cn+Pl的顶点数为2n+l-2=8k+2t-1，边数为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可得以下结果：

引理3 当n=4k，l=2t+1时，哑铃图2Cn+Pl的顶点集与集合{0，1，2，…，16k+4t-1}构成单射.

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

引理4 当n=4k，l=2t+1时，哑铃图2Cn+Pl的边集与集合{1，3，5，…，16k+4t-1}构成一一对应．

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

再由引理3、引理4及定义1知，情形2成立，即当n=4k，l=2t+1时，哑铃图2Cn+Pl是奇优美图.

定理1 当n=4k时，哑铃图2Cn+Pl是奇优美图．

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

情形3 当n=4k+2，l=2t时，哑铃图2Cn+Pl是奇优美图．

当n=4k+2，l=2t时，哑铃图2Cn+Pl的顶点数为2n+l-2=8k+2t+2，边数为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可得以下结果：

引理5 当n=4k+2，l=2t时，哑铃图2Cn+Pl的顶点集与集合{0，1，2，…，16k+4t+5}构成单射.

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

引理6 当n=4k+2，l=2t时，哑铃图2Cn+Pl的边集与集合{1，3，5，…，16k+4t+5}构成一一对应

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

再由引理5、引理6及定义1知，情形3成立，即当n=4k+2，l=2t时，哑铃图2Cn+Pl是奇优美图.

情形4 当n=4k+2，l=2t+1时，哑铃图2Cn+Pl是奇优美图．

当n=4k+2，l=2t+1时，哑铃图2Cn+Pl的顶点数为2n+l-2=8k+2t+3，边数为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可得以下结果：

引理7 当n=4k+2，l=2t+1时，哑铃图2Cn+Pl的顶点集与集合{0，1，2，…，16k+4t+7}构成单射．

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

引理8 当n=4k+2，l=2t+1时，哑铃图2Cn+Pl的边集与集合{1，3，5，…，16k+4t+7}构成一一对应．

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

再由引理7、引理8及定义1知，情形4成立，即当n=4k+2，l=2t+1时，哑铃图2Cn+Pl是奇优美图.

定理2 当n=4k+2时，哑铃图2Cn+Pl是奇优美图．

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

2 定理3的证明

情形5 当n=4k，l=2t时，哑铃图2Cn+Pl是奇强协调图．

当n=4k，l=2t时，哑铃图2Cn+Pl的顶点数为2n+l-2=8k+2t-2，边数为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可得以下结果：

引理9 当n=4k，l=2t时，哑铃图2Cn+Pl的顶点集与集合{0，1，2，…，16k+4t-3}构成单射．

证明 仿引理1的证明，当n=4k，l=2t时，哑铃图2Cn+Pl中各顶点的标号均不相同.又顶点标号中的最小数是0（由算法的（1）知），最大数8k+2t+1是（由算法的（5）知），显然小于16k+4t-3.所以，当n=4k，l= 2t时，哑铃图2Cn+Pl的顶点集与集合构成单射．

引理10 当n=4k，l=2t时，哑铃图2Cn+Pl的边集与集合{1，3，5，…，16k+4t-3}构成一一对应．

证明 由算法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各边的标号均不相同，且全为奇数.即当n=4k，l=2t时，哑铃图2Cn+Pl的边集与集合{1，3，5，…，16k+4t+3}构成一一对应.

由引理9、引理10及定义2知，情形5成立，即当n=4k，l=2t时，哑铃图2Cn+Pl是奇强协调图.

情形6 当n=4k，l=2t+1时，哑铃图2Cn+Pl是奇强协调图．

当n=4k，l=2t+1时，哑铃图2Cn+Pl的顶点数为2n+l-2=8k+2t-1，边数为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．

按照算法可得以下结果：

引理11 当n=4k，l=2t+1时，哑铃图2Cn+Pl的顶点集与集合{0，1，2，…，16k+4t-1}构成单射．

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

引理12 当n=4k，l=2t+1时，哑铃图2Cn+Pl的边集与集合{1，3，5，…，16k+4t-1}构成一一对应．

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

由引理11、引理12及定义2知，情形6成立，即当n=4k，l=2t+1时，哑铃图2Cn+Pl是奇强协调图.

定理3 当n=4k时，哑铃图2Cn+Pl是奇强协调图.

证明 由情形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]林育青.一类图的优美性[J].云南师范大学学报:自然科学版,2004,24(4):15-19.

[8]林育青.Cn与1Cn的优美标号[J].安徽大学学报:自然科学版,2007,32(2):13-16.

[9]林育青,钟发胜,童细心,等.图的奇优美标号算法[J].数学理论与应用,2013,33(4):29-34.

[10]林育青,张玲瑛,钟发胜,等.关于奇优美图及奇强协调图的一点注记[J].贵州师范大学学报:自然科学版,2014,32 (2):43-46.

[11]张玲瑛,林育青,钟发胜,等.关于图2×Cn的标号[J].北华大学学报:自然科学版,2014,15(2):174-178.

[13]童细心,林育青,钟发胜.圈Cn的奇优美性和奇强协调性[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

汕头职业技术学院2014年院级科研课题（SZK2014Y24）