圖ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的優美性

張政，胡紅亮

（西安航空學院理學院，陜西西安710077）

圖ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的優美性

張政，胡紅亮

（西安航空學院理學院，陜西西安710077）

給出了ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的定義，討論了ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的優美性，用構造性的方法給出了一些特殊的ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠的優美標號。證明了一些特殊的ω4g,4h+3的（r1,r2,…,r4g,4h+2）-冠是交錯圖。

圈；冠；優美圖；交錯圖

1 引言與概念

優美圖是圖論中極有趣的研究課題，有著較好的應用價值和廣闊的研究前景。它的研究是從1963年GRingel提出的一個猜想和1966年A Rosa的一篇論文開始的。1972年，SW Golomb明確給出了優美圖的定義。近幾十年，國內外獲得不少關于優美圖的研究成果，它們被應用于射電天文學，X-射線衍射晶體學，密碼設計，通信網絡編址，導彈控制碼設計，同步機碼設計等領域。

文中所討論的圖均為無向簡單圖，V(G)和E(G)分別表示圖G的頂點集和邊集，未說明的符號及術語均見文［1］。

定義1［1］對于一個簡單圖G=V(G),E(G)=(V,E)，如果對每一個頂點v∈V，存在一個非負整數θ(v)（稱為頂點v的標號）使滿足：

①?u,v∈V，若u≠v，則θ(u)≠θ(v)。②max{θ(v)|v∈V}=|E|。③?e1,e2∈E，若e1≠e2，則θ'(e1)≠θ'(e2)。其中：θ'(e)=|θ(u)-θ(v)|，e=uv（稱θ'(e)為邊e的標號），則G稱為優美圖，θ(v)稱為G的一個優美標號。

定義2［1］在圖G每個頂點都粘接了r條懸掛邊（r≥1的整數）所得到的圖，稱為圖G的r-冠，圖G的1-冠，稱作圖G的冠。

定義3V(G)={v1,v2,...,vn}的每個頂點vi都粘接了ri條懸掛邊（ri≥0的整數，i=1,2,...,n）所得到的圖，稱為圖G的(r1,r2,...,rn)-冠，簡記為G(r1,r2,...,rn)。特別地，當r1=r2=...=rn=r時，稱為圖G的r-冠。圖G的0-冠就是圖G。

定義4［1］由圈Cm和Cn恰有一個公共點所組成的圖記為圖ωm,n。

定義5［2］G是一個優美二部圖，其優美標號為θ，V(G)劃分成兩個集合X,Y，如果maxθ(v)＜minθ(v)，則稱θ是G的交錯標號，稱G是在交錯標號θ下的交錯圖。

文獻［1］中證明了P1∨Pn及其r-冠是優美的，從而猜測：任意優美圖的r-冠都是優美的，在此猜想的指導下，文獻［3-5］中證明了：當n≡0,3(mod4)時，圖Cn及其r-冠是優美圖；文獻［6-8］中給出了圖Cn的(r1,r2,...,rn)-冠的定義，討論了n=3,7,8,11,4h,4h+3時，圖Cn的(r1,r2,...,rn)-冠的優美性；文獻［10-12］給出了ωm,n的(r1,r2,...,rm+n-1)-冠的定義，討論了(m,n)=(4,4),(4,6),(5,6),(5,7)時，圖ωm,n的(r1,r2,...,rm+n-1)-冠的優美性。本文證明了圖ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠的優美性，并給出了4種不同的優美標號，同時證明了這些優美標號也是交錯標號。

2 主要結果及其證明

定理當m=4g，n=4h+3，g和h為任意自然數，ri為任意非負整數（i=1,2,...,m+n-1），圖ωm,n的(r1,r2,...,rm+n-1)-冠的頂點集如圖1所示，V(ωm,n)=(v1,v2,...,vm,vm+1,...,vm+n-1)，與vi鄰接的懸掛邊（或葉）記為xij（vi∈V(ωm,n)，j=1,2,...,ri），當時，ωm,n的(r1,r2,...,rm+n-1)-冠是優美圖且為交錯圖。

圖1 ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠Fig.1 The(r1,r2,...,r4g+4h+2)-corona of the graphω4g,4h+3

第1種優美（交錯）標號：

容易驗證：

θ:V（ω4g,4h+3的() r1,r2,...,r4g+4h+2-冠）→是一個單射。

因此，θ是ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠的交錯標號。即ω4g,4h+3的(r1,r2,...,r4g+4h+2)-冠是交錯圖。第2種優美（交錯）標號：

第3種優美（交錯）標號：

第4種優美（交錯）標號：

第2、3、4種優美交錯標號的證明類似于第1種優美交錯標號，此處略。

例下面根據定理給出ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2)-冠的4種交錯標號，如圖2～圖5所示。

圖2 圖ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2) -冠的第1種交錯標號Fig.2 The firstalternating labeling of the (1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2) -corona of the graphω8,11

圖3 圖ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2) -冠的第2種交錯標號Fig.3 The second alternating labeling of the (1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2) -corona of the graphω8,11

圖4 圖ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2)-冠的第3種交錯標號Fig.4 The third alternating labeling of the(1,2,3,2, 3,1,1,2,2,1,3,2,1,2,1,2,3,2)-corona of the graphω8,11

圖5 圖ω8,11的(1,2,3,2,3,1,1,2,2,1,3,2,1,2,1,2,3,2)-冠的第4種交錯標號Fig.5 The fourth alternating labeling of the(1,2,3,2, 3,1,1,2,2,1,3,2,1,2,1,2,3,2)-corona of the graphω8,11

[1]馬克杰.優美圖[M].北京:北京大學出版社,1991:10-15.

[2]楊顯文,張志尚.一類交r錯圖并的優美性[J].吉林工程技術師范學院學報:自然科學版,2007,23(6):8-10.

[3]武建春.圖D2,4k與它的-冠的優美性[J].內蒙古電大學刊,2002(1):34.

[4]曾朝英,武建春.關于優美圖Cn和r¤k1的r-冠的優美性[J].集寧師專學報2000,22(4):4-7.

[5]胡紅亮.圖Cn的r-冠的新的優美標號[J].純粹數學與應用數學[J].2010,26(3):454-457.

[6]吳躍生,李詠秋.關于圈Cn的(r1,r2,...,rn)-冠(n=7,8)的優美性[J].阜陽師范學院學報:自然科學版,2010,27(3):20-23.

[7]吳躍生,李詠秋.再探圈Cn的(r1,r2,...,rn)-冠(n=7,8)的優美性[J].阜陽師范學院學報:自然科學版,2010,27(4):1-4.

[8]吳躍生.關于圈C4h的(r1,r2,...,r4h)-冠的優美性[J].華東交通大學學報,2011,28(1):77-80.

[9]曾朝英.圖ω4k,n的r-冠的優美性[J].集寧師專學報,2001,23(4):4-6.

[10]吳躍生,李詠秋.關于圖ω4,4的(r1,r2,...,r7)-冠的優美性[J].宜春學院學報,2010,32(12):1-3.

[11]吳躍生.關于圖ω4,6的(r1,r2,...,r9)-冠的優美性[J].宜春學院學報,2011,33(8):1-3.

[12]吳躍生,李詠秋.關于圖ω5,6的(r1,r2,...,r10)-冠的優美性[J].北京聯合大學學報,2011,25(2):60-61.

[13]吳躍生,李詠秋.關于圖ω5,7的(r1,r2,...,r11)-冠的優美性[J].嘉應學院學報,2011,29(5):5-8.

[14]吳躍生,王廣富,徐保根.關于圖C4h+1⊙k1的(Gr1,Gr2,Gr3,...,Gr4h+2)-冠的優美性[J].山東大學學報:理學版,2013,48(4):25-28.

On the Gracefulnessof the() r1,r2,...,r4g+4h+2-corona of the Graphω4g,4h+3

Zhang Zheng,Hu Hongliang
(Schoolof Science,Xi’an AeronauticalUniversity,Xi’an 710077,China)

A definition hasbeen given for the(r1,r2,...,r4g+4h+2) -corona of the graphω4g,4h+3.The gracefulnessof the (r1,r2,...,r4g+4h+2) -corona of the graphω4g,4h+3is then discussed and the graceful labeling is presented in this paper. Italso proves thatsome special(r1,r2,...,r4g+4h+2) -corona of the graphω4g,4h+3are ofalternating graph.

cycle;corona;gracefulgraph;alternating graph

O157.5

A

2014-06-23

國家自然科學基金（11171273）

張政（1981—），男，講師，研究方向為圖論及其應用。

1005-0523（2014）05-0117-05