一類啞鈴圖的優美性和奇強協調性

童細心

（廣東省汕頭職業技術學院自然科學系，廣東汕頭515041）

一類啞鈴圖的優美性和奇強協調性

童細心

（廣東省汕頭職業技術學院自然科學系，廣東汕頭515041）

研究了啞鈴圖2Cn+{unv1}的優美性和奇強協調性，得到了啞鈴圖2Cn+{unv1}在n=4k時是優美圖和奇強協調圖等結論.

啞鈴圖；優美圖；奇強協調圖

0 引言

圖論是數學的一個重要分支，而優美圖作為圖論的一個重要內容，由于它應用的廣泛性，一直是人們研究的熱點，也取得了很多研究成果[1-14].1991年，Gnanajoethi提出另一個猜想：“每棵樹都是奇優美的”[3]，1982年，Fank Hsu D[4]引入圖的強協調標號.由于缺乏一個系統和有力的工具，迄今，只能對一些特殊圖探索其優美性、奇優美性及奇強協調性.文獻[14]中給出了啞鈴圖2Cn+{unν1}的奇優美性.本文進一步研究了其優美性和奇強協調性，得到了如下結果.

定理1：當n=4k時，啞鈴圖2Cn+{unν1}是優美圖.

定理2：當n=4k時，啞鈴圖2Cn+{unν1}是奇強協調圖.

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

定義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}的一個一一對應，則稱圖G是奇強協調圖，f為圖G的奇強協調標號.

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

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

圖1 啞鈴圖Cn+Cm+Pl

1 定理1的證明

當n=4k時，啞鈴圖2Cn+{unν1}的頂點數為2n=8k，邊數|E|=2n+1=8k+1.當n=4k時，給出啞鈴圖2Cn+{unν1}的各頂點標號算法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可得以下結果.

引理1：當n=4k時，啞鈴圖2Cn+{unν1}的頂點集與集合{0，1，2，…，8k+1}構成單射.

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

引理2：當n=4k時，啞鈴圖2Cn+{unν1}的邊集與集合{1，2，3，…，8k+1}構成一一對應.

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

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

（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中邊的標號有以下幾種情況：

（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中，各邊的標號范圍為：

（1）2k+2≤u2i-1u2i≤4k，且標號為偶數，其中i=1，2，…，k；

（2）2k+1≤u2iu2i+1≤4k-1，且標號為奇數，其中i=1，2，…，k；

（3）1≤u2i-1u2i≤2k-1，且標號為奇數，其中i=k+1，k+2，…，2k；

（4）2≤u2iu2i+1≤2k-2，且標號為偶數，其中i=k+1，k+2，…，2k-1；

（5）u4ku1=2k；

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

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

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

（1）6k+3≤ν2i-1ν2i≤8k+1，且標號為奇數，其中i=1，2，…，k；

（2）6k+4≤ν2iν2i+1≤8k，且標號為偶數，其中i=1，2，…，k-1；

（3）4k+2≤ν2i-1ν2i+2≤6k，且標號為偶數，其中i=k+1，k+2，…，2k；

（4）4k+3≤ν2iν2i+1≤6k+1，且標號為奇數，其中i=k，k+1，…，2k-1；

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

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

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

綜上所述，當n=4k時，啞鈴圖2Cn+{unν1}中的各邊的標號均不相同.即當n=4k時，啞鈴圖2Cn+{unν1}的邊集與集合{1，2，3，…，8k+1}構成一一對應.

定理1：當n=4k時，啞鈴圖2Cn+{unv1}是優美圖.

證明：由引理1、引理2可得當n=4k時，啞鈴圖2Cn+{unν1}存在優美標號，由定義1，當n=4k時，啞鈴圖2Cn+{unν1}是優美圖，即定理1得證.

2 定理2的證明

當n=4k時，啞鈴圖2Cn+{unν1}的頂點數為2n=8k，邊數為2n+1=8k+1，此時2|E|-1=16k+1.當n=4k時，我們給出啞鈴圖2Cn+{unν1}的各頂點的標號遞推算法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得到如下結論.

引理3當n=4k時，啞鈴圖2Cn+{unν1}的頂點集與集合{0，1，2，…，16k+1}構成單射.

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

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

引理4啞鈴圖2Cn+{unν1}的邊集與集合{1，3，5，…，16k+1}構成一一對應.

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

（一）由算法B的（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，…，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中邊的標號有以下幾種情況：

（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中，各邊的標號均為奇數，都是以4為公差的等

差數列，且范圍為：

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

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

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

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

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

同樣，由邊的標號范圍及等差數列的性質知，在ν1ν2…ν4kν1中，各邊的標號不相等.

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

綜上所述，當n=4k時，啞鈴圖2Cn+{unν1}各邊的標號均不相同，且全為奇數.即當n=4k時，啞鈴圖2Cn+{unν1}的邊集與集合{1，3，5，…，16k+1}構成一一對應.

定理2：當n=4k時，啞鈴圖2Cn+{unν1}是奇強協調圖.

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

3 注記

按照算法A、B，分別得到啞鈴圖2C8+{u8ν1}的優美標號（圖2）和奇強協調標號（圖3）如下：

圖2 啞鈴圖2C8+{u8ν1}的優美標號

圖3 啞鈴圖2C8+{u8ν1}的奇強協調標號

[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]林育青.關于圖Pn3的優美性[J].華南師范大學學報：自然科學版，2000（3）：21-24.

[6]鄧懷敏，林育青.關于圖Pn3的優美標號[J].新疆大學學報：自然科學版，2000，17（2）：12-16.

[7]林育青.一類圖的優美性[J].云南師范大學學報：自然科學版，2004，24（4）：15-19.

[8]林育青.Cn與1Cn的優美標號[J].安徽大學學報：自然科學版，2007，32（2）：13-16.

[9]林育青，鐘發勝，童細心，等.圖Pn3的奇優美標號算法[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]劉家保，王林，陸一南.雙圈圖G（n，m）的奇優美標號及其算法[J].合肥工業大學學報：自然科學版，2012，35（5）：708-710.

[15]馬克杰.優美圖[M].北京：北京大學出版社，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

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

汕頭職業技術學院重點資助課題（SZK2013Z1）