基于路P8m+4t+2的交錯標號的圖S(4m+1,4(t+1),4m-1)的優(yōu)美標號*

吳躍生

(華東交通大學理學院，江西 南昌330013)

?

基于路P8m+4t+2的交錯標號的圖S(4m+1,4(t+1),4m-1)的優(yōu)美標號*

吳躍生

(華東交通大學理學院，江西 南昌330013)

給出了圖S(4m+1,4(t+1),4m-1)的定義；討論了圖S(4m+1,4(t+1),4m-1)的優(yōu)美性，證明了圖S(4m+1,4(t+1),4m-1)是優(yōu)美圖；給出了由路P8m+4t+2的交錯標號構造圖S(4m+1,4(t+1),4m-1)的優(yōu)美標號的四種算法。

優(yōu)美圖；交錯圖；優(yōu)美標號；交錯標號；路；圈

圖的優(yōu)美標號問題是組合數(shù)學中一個熱門課題[1-17]。1988年，Rosa給出了三角仙人掌，四角仙人掌，五角仙人掌等概念；1989年Mouton對三角仙人掌的特殊情形三角蛇的優(yōu)美性給出了證明[2]。

1 若干概念

定義1[2]所有的塊皆為Cm的連通圖，稱為m角仙人掌(或稱Cm仙人掌)。

定義2[2]在頂點最大度為4的m角仙人掌中，如果每個Cm至多有二個度為4的點，且度為4的點構成一條簡單通路，則稱此m角仙人掌為Cm蛇。

定義3 塊分別為Cm,Cn,Cq的連通圖，稱為(m,n,q)角仙人掌。

定義4 在頂點最大度為4的(m,n,q)角仙人掌中，如果Cm,Cn,Cq至多有二個度為4的點，且度為4的點構成一條簡單通路，則稱此(m,n,q)角仙人掌為(m,n,q)蛇。記為S(m,n,q)。

本文討論了圖S(4m+1,4(t+1),4m-1)的優(yōu)美性。

2 主要結果及其證明

定理1 對任意自然數(shù)m,t(m≥1)，圖S(4m+1,4(t+1),4m-1)存在缺標號值 5m+2t+1,5m+2t+2和6m+3t+3的優(yōu)美標號。

證明 設V(C4m+1)={u0,u1,u2，…,u4m}，

定義圖S(4m+1,4(t+1),4m-1)的標號θ為

下面證明θ是圖S(4m+1,4(t+1),4m-1)的優(yōu)美標號。

1)θ:{u2i+1:i=0,1,2,…,4m+2t}→

[4m+2t+1,8m+4t+4]-

{5m+2t+1,5m+2t+2,6m+3t+3}

是雙射;

是雙射;所以

θ:V(S(4m+1,4(t+1),4m-1))→

[0,8m+4t+2]-{5m+2t+1,5m+

2t+2,6m+3t+3}

是雙射;

2)

θ′(u2i+1u2i+2)=

θ′(u2i+1u2i)=

θ′:E(C4(t+1))→[4m+1,4m+4t+4}是雙射；

θ′(u8m+4t+1u4m+4t+3)=2m+1;

θ′:E(C4m-1)→[1,2m-1]∪[2m+1,4m]是雙射；

θ′：E(S(4m+1,4(t+1),4m-1))→[1, 8m+4t+4]是一一對應

由1)和2)可知θ就是圖S(4m+1,4(t+1),4m-1)缺標號值5m+2t+1,5m+2t+2和6m+3t+3的優(yōu)美標號。證畢。

由定理1可給出圖S(4m+1,4(t+1),4m-1)的優(yōu)美標號的第一種算法：

第一步：先給出路P8m+4t+2的交錯標號θ如下：設

第二步：將路P8m+4t+2的交錯標號值不小于6m+3t+1的均加3,將路P8m+4t+2的交錯標號值不小于5m+2t+1不大于6m+3t的均加2，其余的交錯標號值不變；

第三步：在路P8m+4t+2中的頂點u0和u4m之間加連一條邊(在標號值為0,2m的兩個頂點之間加連一條邊)，在路P8m+4t+2中的頂點u4m和u4m+4t+3之間加連一條邊(在標號值為2m,6m+2t+2,的兩個頂點之間加連一條邊)，路P8m+4t+2中的頂點u4m+4t+3和u8m+4t+1之間加連一條邊(在標號值為4m+2t+1,6m+2t+2的兩個頂點之間加連一條邊)。

例1 當m=2，t=1時，由定理1圖S(9,8,7)的優(yōu)美標號的第一種算法如下：

第一步：先給出路P22的交錯標號如圖1所示；

圖1 路P22的交錯標號Fig.1 The alternating graceful labeling of P22

第二步：將路P22的交錯標號值不小于16的均加3,將路P22的交錯標號值不小于13不大于15的均加2，其余的交錯標號值不變；

第三步：在路P22中的頂點u0和u8之間加連一條邊(在標號值為0,4的兩個頂點之間加連一條邊) 在路P22中的頂點u8和u15之間加連一條邊(在標號值為4,16的兩個頂點之間加連一條邊),在路P22中的頂點u15和u21之間加連一條邊(在標號值為11，16兩個頂點之間加連一條邊)。

由此得到圖S(9,8,7)缺標號值13，14和18的優(yōu)美標號，圖S(9,8,7)缺標號值13，14和18的優(yōu)美標號如圖2所示。

圖2 圖S(9,8,7)的第一種優(yōu)美標號Fig.2 The first graceful labeling of S(9,8,7)

定理2 對任意自然數(shù)m,t(m≥2)，圖S(4m+1,4(t+1),4m-1)存在缺標號值 3m+2t+2,3m+2t+3和6m+3t+3的優(yōu)美標號。

證明 設V(C4m+1)={u0,u1,u2，…,u4m}，

E(C4m+1)={u0u1,u1u2，…,u4m-1u4m,u4mu0},

V(C4(t+1))={u4m,u4m+1,…,u4m+4t+3},

E(C4(t+1))={u4mu4m+1,u4m+u4m+2,…,

u4m+4t+2u4m+4t+3,u4m+4t+3u4m},

V(C4m-1)={u4m+4t+3,u4m+4t+4,…,u8m+4t+1},

E(C4m-1)={u4m+4t+3u4m+4t+4,u4m+4t+4u4m+4t+5,…,

u8m+4tu8m+4t+1,u8m+4t+1u4m+4t+3},

定義圖S(4m+1,4(t+1),4m-1)的標號θ為：

由定理2可給出圖S(4m+1,4(t+1),4m-1)的優(yōu)美標號的第二種算法：

第一步：先給出路P8m+4t+2的如圖1所示的交錯標號。

第二步：將路P8m+4t+2的交錯標號值不小于6m+3t+1的均加3,將路P8m+4t+2的交錯標號值不小于3m+2t+2不大于6m+3t的均加2，其余的交錯標號值不變；

第三步：在路P8m+4t+2中的頂點u0和u4m之間加連一條邊(在標號值為0,2m的兩個頂點之間加連一條邊)，在路P8m+4t+2中的頂點u4m和u4m+4t+3之間加連一條邊(在標號值為2m,6m+2t+2,的兩個頂點之間加連一條邊)，路P8m+4t+2中的頂點u4m+4t+3和u8m+4t+1之間加連一條邊(在標號值為4m+2t+3,6m+2t+2的兩個頂點之間加連一條邊)。

例2 當m=2，t=1時，由定理2圖S(9,8,7)的優(yōu)美標號的第二種算法如下：

第一步：先給出路P22的交錯標號如圖1所示；

第二步：將路P22的交錯標號值不小于16的均加3,將路P22的交錯標號值不小于10不大于15的均加2，其余的交錯標號值不變；

第三步：在路P22中的頂點u0和u8之間加連一條邊(在標號值為0,4的兩個頂點之間加連一條邊) 在路P22中的頂點u8和u15之間加連一條邊(在標號值為4,16的兩個頂點之間加連一條邊),在路P22中的頂點u15和u21之間加連一條邊(在標號值為13，16兩個頂點之間加連一條邊)。

由此得到圖S(9,8,7)缺標號值10,11和18的優(yōu)美標號，圖S(9,8,7)缺標號值10,11和18的優(yōu)美標號如圖3所示。

圖3 圖S(9,8,7)的第二種優(yōu)美標號Fig.3 The second graceful labeling of S(9,8,7)

定理3 對任意自然數(shù)m,t(m≥2)，圖S(4m+1,4(t+1),4m-1)存在缺標號值 3m+2t+3,3m+2t+4和2m+t+1的優(yōu)美標號。

證明 設V(C4m+1)={u0,u1,u2，…,u4m}，

E(C4m+1)={u0u1,u1u2，…,u4m-1u4m,u4mu0},

V(C4(t+1))={u4m,u4m+1,…,u4m+4t+3},

E(C4(t+1))={u4mu4m+1,u4m+u4m+2,…,

u4m+4t+2u4m+4t+3,u4m+4t+3u4m},

V(C4m-1)={u4m+4t+3,u4m+4t+4,…,u8m+4t+1},

E(C4m-1)={u4m+4t+3u4m+4t+4,u4m+4t+4u4m+4t+5,…,

u8m+4tu8m+4t+1,u8m+4t+1u4m+4t+3},

定義圖S(4m+1,4(t+1),4m-1)的標號θ為：

仿定理1,可以驗證θ是圖S(4m+1,4(t+1),4m-1)的缺標號值 3m+2t+2,3m+2t+3和6m+3t+3的優(yōu)美標號。證畢。

由定理3可給出圖S(4m+1,4(t+1),4m-1)的優(yōu)美標號的第三種算法：

第一步：先給出路P8m+4t+2的如圖1所示的交錯標號。

第二步：將路P8m+4t+2的交錯標號值不小于3m+2t+2的均加3,將路P8m+4t+2的交錯標號值不小于2m+t+1不大于3m+2t+1的均加1，其余的交錯標號值不變；

第三步：在路P8m+4t+2中的頂點u0和u4m之間加連一條邊(在標號值為0,2m的兩個頂點之間加連一條邊)，在路P8m+4t+2中的頂點u4m和u4m+4t+3之間加連一條邊(在標號值為2m,6m+2t+3,的兩個頂點之間加連一條邊)，路P8m+4t+2中的頂點u4m+4t+3和u8m+4t+1之間加連一條邊(在標號值為4m+2t+4,6m+2t+3的兩個頂點之間加連一條邊)。

例3 當m=2，t=1時，由定理2圖S(9,8,7)的優(yōu)美標號的第二種算法如下：

第一步：先給出路P22的交錯標號如圖1所示；

第二步：將路P22的交錯標號值不小于10的均加3,將路P22的交錯標號值不小于6不大于9的均加1，其余的交錯標號值不變；

第三步：在路P22中的頂點u0和u8之間加連一條邊(在標號值為0,4的兩個頂點之間加連一條邊) 在路P22中的頂點u8和u15之間加連一條邊(在標號值為4,17的兩個頂點之間加連一條邊),在路P22中的頂點u15和u21之間加連一條邊(在標號值為14,17兩個頂點之間加連一條邊)。

由此得到圖S(9,8,7)缺標號值11,12和6的優(yōu)美標號，圖S(9,8,7)缺標號值11,12和6的優(yōu)美標號如圖4所示。

圖4 圖S(9,8,7)的第三種優(yōu)美標號Fig.4 The third graceful labeling of S(9,8,7)

定理4 對任意自然數(shù)m,t(m≥2)，圖S(4m+1,4(t+1),4m-1)存在缺標號值 5m+2t+2,5m+2t+3和2m+t+1的優(yōu)美標號。

證明 設V(C4m+1)={u0,u1,u2，…,u4m}，

E(C4m+1)={u0u1,u1u2，…,u4m-1u4m,u4mu0},

V(C4(t+1))={u4m,u4m+1,…,u4m+4t+3},

E(C4(t+1))={u4mu4m+1,u4m+u4m+2,…,

u4m+4t+2u4m+4t+3,u4m+4t+3u4m}

V(C4m-1)={u4m+4t+3,u4m+4t+4,…,u8m+4t+1},

E(C4m-1)={u4m+4t+3u4m+4t+4,u4m+4t+4u4m+4t+5,…,

u8m+4tu8m+4t+1,u8m+4t+1u4m+4t+3},

定義圖S(4m+1,4(t+1),4m-1)的標號θ為：

仿定理1,可以驗證θ是圖S(4m+1,4(t+1),4m-1)的缺標號值 5m+2t+2,5m+2t+3和2m+t+1的優(yōu)美標號。證畢。

由定理4可給出圖S(4m+1,4(t+1),4m-1)的優(yōu)美標號的第四種算法：

第一步：先給出路P8m+4t+2的如圖1所示的交錯標號；

第二步：將路P8m+4t+2的交錯標號值不小于5m+2t+1的均加3,將路P8m+4t+2的交錯標號值不小于2m+t+1不大于5m+2t的均加1，其余的交錯標號值不變；

第三步：在路P8m+4t+2中的頂點u0和u4m之間加連一條邊(在標號值為0,2m的兩個頂點之間加連一條邊)，在路P8m+4t+2中的頂點u4m和u4m+4t+3之間加連一條邊(在標號值為2m,6m+2t+3,的兩個頂點之間加連一條邊)，路P8m+4t+2中的頂點u4m+4t+3和u8m+4t+1之間加連一條邊(在標號值為4m+2t+2,6m+2t+3的兩個頂點之間加連一條邊)。

圖5 圖S(9,8,7)的第四種優(yōu)美標號Fig.5 The fourth graceful labeling of S(9,8,7)

例4 當m=2，t=1時，由定理2圖S(9,8,7)的優(yōu)美標號的第二種算法如下：

第一步：先給出路P22的交錯標號如圖1所示；

第二步：將路P22的交錯標號值不小于13的均加3,將路P22的交錯標號值不小于6不大于12的均加1，其余的交錯標號值不變；

第三步：在路P22中的頂點u0和u8之間加連一條邊(在標號值為0,4的兩個頂點之間加連一條邊) 在路P22中的頂點u8和u15之間加連一條邊(在標號值為4,17的兩個頂點之間加連一條邊),在路P22中的頂點u15和u21之間加連一條邊(在標號值為12,17兩個頂點之間加連一條邊)。

由此得到圖S(9,8,7)缺標號值14,15和6的優(yōu)美標號，圖S(9,8,7)缺標號值14,15和6的優(yōu)美標號如圖5所示。

[1] 馬克杰. 優(yōu)美圖[M]. 北京：北京大學出版社，1991: 1-247.

[2] 何梅. 圖2Cn的優(yōu)美性[J]. 內蒙古大學學報：自然科學版，1995, 26(3): 247-251.

[3] 楊顯文. 關于C4m蛇的優(yōu)美性[J]. 工程數(shù)學學報，1995, 12(4): 108-112.

[4] 吳躍生, 李詠秋. 關于圈C4h+3的(r1, r2,…,r4h+3)-冠的優(yōu)美性[J]. 吉首大學學報：自然科學版，2011, 32(6): 1-4.

[6] 吳躍生. 圖C7(r1,r2,r3, ,r4,r5,0,0)∪St(m )的優(yōu)美性[J]. 吉首大學學報：自然科學版， 2012, 33(5): 9-11,25.

[7] 吳躍生. 關于圈C4h+3的(Gr1, Gr2,…,Gr4h+3)-冠的優(yōu)美性[J]. 吉首大學學報：自然科學版，2013, 34(4): 4-9.

[8] GALLIAN J A. A dynamic survey of graph labeling [J]. The Electronic Joumal of Combinatorics, 2013,19, DS6:1-306.

[9] 吳躍生. 連通圖G+e∪Hk-1的優(yōu)美性[J]. 吉首大學學報：自然科學版，2014, 34(2): 3-5.

[10] 吳躍生，王廣富，徐保根. 非連通圖C2n+1(r1,r2, …，rn+1)∪Gm的優(yōu)美性[J]. 西南大學學報：自然科學版，2014, 36(8): 83-86.

[11] 吳躍生.非連通圖C4m-1∪G的優(yōu)美性[J]. 吉首大學學報：自然科學版，2014, 34(3): 1-3.

[12] ABRHAM J，KOTZIG A. All 2-regular graphs consisting of 4-cycles are graceful [J]. Discrete Mathematics, 1994 ,135(1/2/3): 1-14.

[13] 吳躍生，王廣富，徐保根.關于圖G1∪G2⊙K1的優(yōu)美性[J]. 江西師范大學學報：自然科學版，2014, 38(3): 236-239.

[14] 賈慧羨，左大偉. 與扇圖相關的2類圖的超邊優(yōu)美標號[J]. 吉首大學學報：自然科學版，2014, 35(2): 6-9.

[15] 楊思華，姚兵，張婉佳. 一致仙人掌樹的Felicitous性質[J]. 湖南師范大學：自然科學學報，2014, 37(3): 87-90.

[16] 吳躍生. 再探非連通圖C4m-1∪G的優(yōu)美標號[J]. 吉首大學學報：自然科學版，2015, 36(1): 1-4.

[17] 吳躍生. 非連通圖C3(m,0,0)∪G的優(yōu)美性[J]. 華東交通大學學報, 2013, 30(6): 35-39.

The Graceful Labeling of the GraphS(4m+1,4(t+1),4m-1) Based on the Balanced Labeling of the PathP8m+4t+2

WUYuesheng

(School of Science, East China Jiaotong University, Nanchang 330013, China)

A definition of the graphS(4m+1,4(t+1),4m-1) is given. The gracefulness of the graphS(4m+1,4(t+1),4m-1) is discussed. It is proved that ifm≥1,t≥0, the graphS(4m+1,4(t+1),4m-1) is a graceful graph.Based on the alternating labeling ofP8m+4t+2, four algorithms of the graceful labeling ofS(4m+1,4(t+1),4m-1) are given.

graceful graph; alternating graph ; graceful labeling; alternating labeling; path; cycle

10.13471/j.cnki.acta.snus.2015.05.005

2015-01-20

國家自然科學基金資助項目(11261019,11361024)；江西省教育廳2014年度科學技術研究資助項目(GJJ14380)

吳躍生(1959年生)，男；研究方向：圖論;E-mail:616100567@qq.com

O157.5

A

0529-6579(2015)05-0019-05