童細(xì)心

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

一類啞鈴圖的優(yōu)美性和奇強(qiáng)協(xié)調(diào)性

童細(xì)心

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

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

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

0 引言

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

定理1：當(dāng)n=4k時，啞鈴圖2Cn+{unν1}是優(yōu)美圖.

定理2：當(dāng)n=4k時，啞鈴圖2Cn+{unν1}是奇強(qiáng)協(xié)調(diào)圖.

定義1[14]：一個簡單圖G＝（V，E）（V，E分別是G的頂點(diǎn)集與邊集）稱為優(yōu)美的，如果存在一個單射f:V（G）→{0，1，2，…，｜E｜}，使得對所有的邊uν=e∈E（G），由f*（uν）=|f（u）-f（v）|導(dǎo)出的映射f*:V（G）→{1，2，…，｜E｜}是一個一一對應(yīng)，f稱為G的優(yōu)美標(biāo)號.

定義2[4]：對于一個簡單圖G＝（V，E），若存在映射：f:V（G）→{0，1，…，2｜E｜-1}，滿足：（1）f是單射；（2）uν∈E（G），令f（uν）＝f（u）+f（ν），有f是E（G）到{1，3，5，…，2｜E｜-1}的一個一一對應(yīng)，則稱圖G是奇強(qiáng)協(xié)調(diào)圖，f為圖G的奇強(qiáng)協(xié)調(diào)標(biāo)號.

定義3[16，17]：在兩個圈Cn（u）=u1u2…unu1和Cm（ν）=ν1ν2…νmν1上，用一條長為l-1的路連接這兩個圈的一對頂點(diǎn)ui，νj所得到的圖類，稱為啞鈴圖，記為Cn+Cm+Pl.

在本文中，我們記連接兩個圈的頂點(diǎn)ui，νj分別為un，ν1（見圖1）.本文僅討論m=n且l=2時的情況，此時啞鈴圖記為2Cn+{unν1}.為敘述方便，本文規(guī)定所討論的圖都是無向簡單圖，ν既表示點(diǎn)ν，也表示點(diǎn)ν的標(biāo)號.uν既表示邊，也表示該邊的標(biāo)號.點(diǎn)ν2p稱為偶點(diǎn)，ν2p-1稱為奇點(diǎn).其他未加說明的定義和符號均來自文獻(xiàn)[18].

圖1 啞鈴圖Cn+Cm+Pl

1 定理1的證明

當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的頂點(diǎn)數(shù)為2n=8k，邊數(shù)|E|=2n+1=8k+1.當(dāng)n=4k時，給出啞鈴圖2Cn+{unν1}的各頂點(diǎn)標(biāo)號算法A如下：

（1）u2i-1=6k-i+2，其中i=1，2，…，2k；

（2）u2i=2k+i，其中i=1，2，…，k；

u2i=2k+i+1，其中i=k+1，…，2k；

（3）ν2i-1=i-1，其中i=1，2，…，k；

ν2i-1=i，其中i=k+1，…，2k；

（4）ν2i=8k-i+2，其中i=1，2，…，2k.

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

引理1：當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的頂點(diǎn)集與集合{0，1，2，…，8k+1}構(gòu)成單射.

證明：當(dāng)n=4k時，記M是啞鈴圖2Cn+{unν1}的所有頂點(diǎn)標(biāo)號集合，由算法A的（1）-（4）易知：

引理2：當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的邊集與集合{1，2，3，…，8k+1}構(gòu)成一一對應(yīng).

證明：我們把邊的標(biāo)號分為三大類來考慮.

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

（1）u2i-1u2i=|6k-i+2-（2k+i）|=4k-2i+2，其中i=1，2，…，k；

（2）u2iu2i+1=|6k-（i+1）+2-（2k+i）|=4k-2i+1，其中i=1，2，…，k；

（3）u2i-1u2i=|6k-i+2-（2k+i+1）|=4k-2i+1，其中i=k+1，k+2，…，2k；

（4）u2iu2i+1=|6k-（i+1）+2-（2k+i+1）]|=4k-2i，其中i=k+1，k+2，…，2k-1；

（5）u4ku1=2k；

（二）由算法A的（2）（3）可知u4kν1=|（2k+2k+1）-（1-1）|=4k+1；

（三）由算法A的（3）（4）可知ν1ν2…ν4kν1中邊的標(biāo)號有以下幾種情況：

（1）ν2i-1ν2i=|8k-i+2-（i+1）|=8k-2i+3，其中i=1，2，…，k；

（2）ν2iν2i+1=|8k-i+2-[（i+1）-1]|=8k-2i+2，其中i=1，2，…，k-1；

（3）ν2i-1ν2i=|8k-i+2-i|=8k-2i+2，其中i=k+1，k+2，…，2k；

（4）ν2iν2i+1=|8k-i+2-（i+1）|=8k-2i+1，其中i=k，k+1，…，2k-1；

（5）ν4kν1=|8k-2k+2-（1-1）|=6k+2.

首先，由（一）易知，在u1u2…u4ku1中，各邊的標(biāo)號范圍為：

（1）2k+2≤u2i-1u2i≤4k，且標(biāo)號為偶數(shù)，其中i=1，2，…，k；

（2）2k+1≤u2iu2i+1≤4k-1，且標(biāo)號為奇數(shù)，其中i=1，2，…，k；

（3）1≤u2i-1u2i≤2k-1，且標(biāo)號為奇數(shù)，其中i=k+1，k+2，…，2k；

（4）2≤u2iu2i+1≤2k-2，且標(biāo)號為偶數(shù)，其中i=k+1，k+2，…，2k-1；

（5）u4ku1=2k；

由邊的標(biāo)號范圍及奇偶性知，在u1u2…u4ku1中各邊的標(biāo)號不相等.

其次，由（二）知，u4kν1=4k+1.

再次，由（三）易知，在ν1ν2…ν4kν1中各邊的標(biāo)號范圍為：

（1）6k+3≤ν2i-1ν2i≤8k+1，且標(biāo)號為奇數(shù)，其中i=1，2，…，k；

（2）6k+4≤ν2iν2i+1≤8k，且標(biāo)號為偶數(shù)，其中i=1，2，…，k-1；

（3）4k+2≤ν2i-1ν2i+2≤6k，且標(biāo)號為偶數(shù)，其中i=k+1，k+2，…，2k；

（4）4k+3≤ν2iν2i+1≤6k+1，且標(biāo)號為奇數(shù)，其中i=k，k+1，…，2k-1；

（5）ν4kν1=6k+2.

同樣，由邊的標(biāo)號范圍及奇偶性知，在ν1ν2…ν4kν1中各邊的標(biāo)號不相等.

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

綜上所述，當(dāng)n=4k時，啞鈴圖2Cn+{unν1}中的各邊的標(biāo)號均不相同.即當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的邊集與集合{1，2，3，…，8k+1}構(gòu)成一一對應(yīng).

定理1：當(dāng)n=4k時，啞鈴圖2Cn+{unv1}是優(yōu)美圖.

證明：由引理1、引理2可得當(dāng)n=4k時，啞鈴圖2Cn+{unν1}存在優(yōu)美標(biāo)號，由定義1，當(dāng)n=4k時，啞鈴圖2Cn+{unν1}是優(yōu)美圖，即定理1得證.

2 定理2的證明

當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的頂點(diǎn)數(shù)為2n=8k，邊數(shù)為2n+1=8k+1，此時2|E|-1=16k+1.當(dāng)n=4k時，我們給出啞鈴圖2Cn+{unν1}的各頂點(diǎn)的標(biāo)號遞推算法B：

（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）ν2i-1=4k+2i-2，i=1，2，…，2k；

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

ν2i=4k+2i+3，i=k+1，k+2，…，2k.

按照算法B得到如下結(jié)論.

引理3當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的頂點(diǎn)集與集合{0，1，2，…，16k+1}構(gòu)成單射.

證明記N是當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的所有頂點(diǎn)標(biāo)號集合，由算法B的（1）-（4）易知：

顯然，N1，N3中的點(diǎn)全是奇點(diǎn)，其標(biāo)號全為偶數(shù)，N2，N4中的點(diǎn)全是偶點(diǎn)，其標(biāo)號數(shù)全為奇數(shù)，且，即當(dāng)n=4k時，啞鈴圖2Cn+{unν1}中各頂點(diǎn)的標(biāo)號均不相同.又所有頂點(diǎn)標(biāo)號的集合N=N1∪N2∪N3∪N4中最小數(shù)是0，最大數(shù)是8k +3（當(dāng)然小于16k+1）.綜上，當(dāng)n=4k時，啞鈴圖2Cn+{unν1}各頂點(diǎn)的標(biāo)號均不相同，所以當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的頂點(diǎn)集與集合{0，1，2，…，16k+1}構(gòu)成單射.

引理4啞鈴圖2Cn+{unν1}的邊集與集合{1，3，5，…，16k+1}構(gòu)成一一對應(yīng).

證明由算法B知，我們把邊的標(biāo)號分為三大類來考慮.

（一）由算法B的（1）（2）可知u1u2…u4ku1中邊的標(biāo)號有以下幾種情況：

（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，…，2k；

（3）u2iu2i+1=2（i+1）-2+2i-1=4i-1，其中i=1，2，…，k；

（4）u2iu2i+1=2（i+1）-2+2i-1=4i+1，其中i=k+1，…，2k-1；

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

（二）由算法B的（2）（3）有：u4kν1=2·2k+1+4k+2×1-2=8k+1；

（三）由算法的（3）（4）可知ν1ν2…ν4kν1中邊的標(biāo)號有以下幾種情況：

（1）ν2i-1ν2i=4k+2i-2+4k+2i+1=8k+4i-1，其中i=1，2，…，k；

（2）ν2i-1ν2i=4k+2i-2+4k+2i+3=8k+4i+1，其中i=k+1，k+2，…，2k；

（3）ν2iν2i+1=4k+2i+1+4k+2（i+1）-2=8k+4i+1，其中i=1，2，…，k；

（4）ν2iν2i+1=4k+2i+3+4k+2（i+1）-2=8k+4i+3，其中i=k+1，k+2，…，2k-1；

（5）ν4kν1=4k+2·2k+3+（4k+2×1-2）=12k+3.

首先，由（一）易知，在u1u2…u4ku1中，各邊的標(biāo)號均為奇數(shù)，都是以4為公差的等

差數(shù)列，且范圍為：

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

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

（3）3≤u2iu2i+1≤4k-1，其中i=1，2，…，k；

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

（5）u4ku1=4k+1；

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

其次，由（二）知，u4kν1=8k+1.

再次，由（三）易知，在ν1ν2…ν4kν1中，各邊的標(biāo)號也均為奇數(shù)且都是以4為公差的等差數(shù)列，且范圍為：

（1）8k+3≤ν2i-1ν2i≤12k-1，其中i=1，2，…，k；

（2）15k+5≤ν2i-1ν2i≤16k+1，其中i=k+1，…，2k；

（3）8k+5≤ν2iν2i+1≤12k+1，其中i=1，2，…，k；

（4）12k+7≤ν2iν2i+1≤16k-1，其中i=k+1，…，2k-1；

（5）ν4kν1=12k+3.

同樣，由邊的標(biāo)號范圍及等差數(shù)列的性質(zhì)知，在ν1ν2…ν4kν1中，各邊的標(biāo)號不相等.

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

綜上所述，當(dāng)n=4k時，啞鈴圖2Cn+{unν1}各邊的標(biāo)號均不相同，且全為奇數(shù).即當(dāng)n=4k時，啞鈴圖2Cn+{unν1}的邊集與集合{1，3，5，…，16k+1}構(gòu)成一一對應(yīng).

定理2：當(dāng)n=4k時，啞鈴圖2Cn+{unν1}是奇強(qiáng)協(xié)調(diào)圖.

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

3 注記

按照算法A、B，分別得到啞鈴圖2C8+{u8ν1}的優(yōu)美標(biāo)號（圖2）和奇強(qiáng)協(xié)調(diào)標(biāo)號（圖3）如下：

圖2 啞鈴圖2C8+{u8ν1}的優(yōu)美標(biāo)號

圖3 啞鈴圖2C8+{u8ν1}的奇強(qiáng)協(xié)調(diào)標(biāo)號

[1]Ringel G.Problem 25，in：theory of graphs and its application[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 in graph theory[D].India：Madurai Kamaraj University，1991.

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

[5]林育青.關(guān)于圖Pn3的優(yōu)美性[J].華南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2000（3）：21-24.

[6]鄧懷敏，林育青.關(guān)于圖Pn3的優(yōu)美標(biāo)號[J].新疆大學(xué)學(xué)報(bào)：自然科學(xué)版，2000，17（2）：12-16.

[7]林育青.一類圖的優(yōu)美性[J].云南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，24（4）：15-19.

[8]林育青.Cn與1Cn的優(yōu)美標(biāo)號[J].安徽大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，32（2）：13-16.

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

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

[11]張玲瑛，林育青，鐘發(fā)勝，等.關(guān)于圖2×Cn的標(biāo)號[J].北華大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，15（2）：174-178.

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

[14]劉家保，王林，陸一南.雙圈圖G（n，m）的奇優(yōu)美標(biāo)號及其算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，35（5）：708-710.

[15]馬克杰.優(yōu)美圖[M].北京：北京大學(xué)出版社，1991.

[16]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.

[17]Tang Z K，Huang G H，Jiang X J，et al.The metric dimension of dumbbell-shape graph[J]. Journal of Natural Science of Hunan Normal University，2013，36（6）：7-10.

[18]Bandy J A，Murty U S R.Graph theory with application[M].New York：American Elsevier Publishing Co Inc，1976.

Gracefulness and Odd Strong Harmoniousness of A K ind of Dumbbell-Shape Graphs

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

Gracefulness and odd strong harmoniousness of dumbbell-shape graphs have been studied.Dumbbell-shape graphs are shown to be graceful and odd strongly Harmonious when n=4k.

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

O 157.5

A

1001-4217（2015）02-0038-06

2014-11-05

童細(xì)心（1979-），男，湖南岳陽人，講師.研究方向：圖論.E-mail：txx2486@126.com

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