非連通圖L6∪G的優美標號

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

·基礎學科·

非連通圖L6∪G的優美標號

吳 躍 生

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

討論非連通圖L6∪G的優美性，給出了非連通圖L6∪G是優美圖的4個充分條件。

優美圖;交錯圖；非連通圖;優美標號;梯圖

1 引言與概念

圖的優美標號問題是組合數學中一個熱門課題[1-20]。

本文討論了非連通圖L6∪G的優美性。

定義2[1]L2m=P2×Pm稱為梯圖。

梯圖L6存在如圖1所示的優美標號。

圖1 梯圖L6的優美標號

梯圖L6存在如圖1所示的特征為2且缺標號值4，6的交錯標號。

2 主要結果及其證明

圖2 圖L6

定義L6∪Gk+2的頂點標號θ為：

θ(v1)=k+9，θ(v2)=k+3，θ(v3)=k+5，θ(v4)=k+4，θ(v5)=k+7,θ(v6)=k+2，

下面證明θ是非連通圖L6∪Gk+2的優美標號。

1)θ:V(L6)→[k+2,k+7]∪{k+9}-{k+6}是雙射，

θ:X→[0,k]是單射(或雙射)，θ:Y→[k+8,q+7]-{k+9}是單射(或雙射);

所以，θ:V(L6∪Gk+2)→[0,q+7]-{k+1，k+6}是單射(或雙射)。

θ′(v3v4)=1,θ′(v4v5)=3,θ′(v6v5)=5,θ′(v6v1)=7，

θ′:E(L6)→[1,7]是雙射，θ′:E(Gk+2)→[8,q+7]是雙射，

所以θ就是非連通圖L6∪Gk+2的缺k+1和k+6標號值的優美標號。

令X1=X∪{v2,v4,v6}，Y1=Y∪{v1,v3,v5}，

則有

所以，θ就是非連通圖L6∪Gk+2的特征為k+4,且缺k+1和k+6標號值的交錯標號。 證畢。

注意到：k+6=(k+4)+2,連續應用定理1。

定義L6∪Gk+2的頂點標號θ為：

θ(v1)=k+6，θ(v2)=k+3，θ(v3)=k+5，θ(v4)=k+4，θ(v5)=k+9,θ(v6)=k+2，

下面證明θ是非連通圖L6∪Gk+2的優美標號。

1)θ:V(L6)→[k+2,k+6]∪{k+9}是雙射，

θ:X→[0,k]是單射(或雙射);θ:Y→[k+8,q+7]-{k+9}是單射(或雙射);

所以θ:V(L6∪Gk+2)→[0,q+7]-{k+1，k+7}是單射(或雙射)。

θ′(v4v5)=5,θ′(v6v5)=7,θ′(v6v1)=4，

θ′:E(L6)→[1,7]是雙射，θ′:E(Gk+2)→[8,q+7]是雙射，

所以θ就是非連通圖L6∪Gk+2的缺k+1和k+7標號值的優美標號。

令X1=X∪{v2,v4,v6}，Y1=Y∪{v1,v3,v5}，

則有

所以，θ就是非連通圖L6∪Gk+2的特征為k+4,且缺k+1和k+7標號值的交錯標號。 證畢。

定義L6∪Gk+3的頂點標號θ為：

θ(v1)=k+7，θ(v2)=k+4，θ(v3)=k+6，θ(v4)=k+5，θ(v5)=k+10,θ(v6)=k+3。

下面證明θ是非連通圖L6∪Gk+3的優美標號。

1)θ:V(L6)→[k+3,k+7]∪{k+10}是雙射，

θ:X→[0,k]是單射(或雙射)，θ:Y→[k+8,q+7]-{k+10}是單射(或雙射);

所以θ:V(L6∪Gk+3)→[0,q+7]-{k+1，k+2}是單射(或雙射)。

θ′(v4v5)=5,θ′(v6v5)=7,θ′(v6v1)=4，

θ′:E(L6)→[1,7]是雙射，θ′:E(Gk+3)→[8,q+7]是雙射，

所以θ就是非連通圖L6∪Gk+3的缺k+1和k+2標號值的優美標號。

令X1=X∪{v2,v4,v6}，Y1=Y∪{v1,v3,v5}，

則有

所以，θ就是非連通圖L6∪Gk+3的特征為k+5,且缺k+1和k+2標號值的交錯標號。 證畢。

定義L6∪Gk+3的頂點標號θ為：

θ(v1)=k+1，θ(v2)=k+4，θ(v3)=k+2，θ(v4)=k+3，θ(v5)=k+10,θ(v6)=k+5。

下面證明θ是非連通圖L6∪Gk+3的優美標號。

1)θ:V(L6)→[k+1,k+5]∪{k+10}是雙射;

θ:X→[0,k]是單射(或雙射);θ:Y→[k+8,q+7]-{k+10}是單射(或雙射);

使用θ:V(L6∪Gk+3)→[0,q+7]-{k+6，k+7}是單射(或雙射)。

θ′(v4v5)=7,θ′(v6v5)=5,θ′(v6v1)=4，

θ′:E(L6)→[1,7]是雙射，θ′:E(Gk+3)→[8,q+7]是雙射，

所以θ就是非連通圖L6∪Gk+3的缺k+6和k+7標號值的優美標號。

定義L6∪Gk+4的頂點標號θ為：

θ(v1)=k+1，θ(v2)=k+5，θ(v3)=k+11，θ(v4)=k+4，θ(v5)=k+3,θ(v6)=k+6，

下面證明θ是非連通圖L6∪Gk+4的優美標號。

1)θ:V(L6)→[k+1,k+6]∪{k+11}-{k+2}是雙射，

θ:X→[0,k]是單射(或雙射)，θ:Y→[k+8,q+7]-{k+11}是單射(或雙射);

所以θ:V(L6∪Gk+4)→[0,q+7]-{k+2，k+7}是單射(或雙射)。

θ′(v4v5)=1,θ′(v6v5)=3,θ′(v6v1)=5，

θ′:E(L6)→[1,7]是雙射，θ′:E(Gk+4)→[8,q+7]是雙射，

所以θ就是非連通圖L6∪G的缺k+2和k+7標號值的優美標號。證畢。

定義L6∪Gk+4的頂點標號θ為：

θ(v1)=k+2，θ(v2)=k+5，θ(v3)=k+3，θ(v4)=k+4，θ(v5)=k+11,θ(v6)=k+6，

下面證明θ是非連通圖L6∪Gk+4的優美標號。

1)θ:V(L6)→[k+2,k+6]∪{k+11}是雙射，

θ:X→[0,k]是單射(或雙射)，θ:Y→[k+8,q+7]-{k+11}是單射(或雙射);

所以θ:V(L6∪Gk+4)→[0,q+7]-{k+1，k+7}是單射(或雙射)。

θ′(v4v5)=7,θ′(v6v5)=5,θ′(v6v1)=4，

θ′:E(L6)→[1,7]是雙射，θ′:E(Gk+4)→[8,q+7]是雙射，

所以θ就是非連通圖L6∪Gk+4的缺k+1和k+7標號值的優美標號。證畢。

定義L6∪Gk+5的頂點標號θ為：

θ(v1)=k+2，θ(v2)=k+6，θ(v3)=k+12，θ(v4)=k+5，θ(v5)=k+4,θ(v6)=k+7，

下面證明θ是非連通圖L6∪Gk+5的優美標號。

1)θ:V(L6)→[k+2,k+7]∪{k+12}-{k+3}是雙射，

θ:X→[0,k]是單射(或雙射)，θ:Y→[k+8,q+7]-{k+12}是單射(或雙射);

所以θ:V(L6∪Gk+5)→[0,q+7]-{k+1，k+3}是單射(或雙射)。

θ′(v4v5)=1,θ′(v6v5)=3,θ′(v6v1)=5，

θ′:E(L6)→[1,7]是雙射，θ′:E(Gk+5)→[8,q+7]是雙射，

所以θ就是非連通圖L6∪Gk+5的缺k+1和k+3標號值的優美標號。證畢。

定義L6∪Gk+5的頂點標號θ為：

θ(v1)=k+3，θ(v2)=k+6，θ(v3)=k+4，θ(v4)=k+5，θ(v5)=k+12,θ(v6)=k+7，

下面證明θ是非連通圖L6∪Gk+5的優美標號。

1)θ:V(L6)→[k+3,k+7]∪{k+12}是雙射，

θ:X→[0,k]是單射(或雙射)，θ:Y→[k+8,q+7]-{k+12}是單射(或雙射);

所以θ:V(L6∪Gk+5)→[0,q+7]-{k+1，k+2}是單射(或雙射)。

θ′(v4v5)=7,θ′(v6v5)=5,θ′(v6v1)=4，

θ′:E(L6)→[1,7]是雙射，θ′:E(Gk+5)→[8,q+7]是雙射，

所以θ就是非連通圖L6∪Gk+5的缺k+1和k+2標號值的優美標號。證畢。

引理1[1]對任意正整數n，設C4n是有4n個頂點的圈，則C4n存在特征為2n-1,且缺3n的交錯標號。

證記圈C4n上的頂點依次為v1,v2,…,v4n，定義圈C4n的頂點標號θ為

容易驗證，θ就是圈C4n的特征為2n-1,且缺3n的交錯標號。

注意到：3n=(2n-1)+n+1，由定理1和引理1有

推論2非連通圖L6∪C4存在特征為5且缺2和7標號值的交錯標號。

由定理2和引理1有

推論3非連通圖L6∪C4存在特征為5且缺2和8標號值的交錯標號。

由定理3和引理1有

推論4非連通圖L6∪C8存在特征為8且缺4和5標號值的交錯標號。

由定理4和引理1有

推論5非連通圖L6∪C8存在缺9和10標號值的優美標號。

由定理5和引理1有

推論6非連通圖L6∪C12存在缺7和12標號值的優美標號。

由定理6和引理1有

推論7非連通圖L6∪C12存在缺6和12標號值的優美標號。

由定理7和引理1有

推論8非連通圖L6∪C16存在缺8和10標號值的優美標號。

由定理8和引理1有

推論9非連通圖L6∪C16存在缺8和9標號值的優美標號。

例非連通圖L6∪C4的交錯標號如圖3、圖4所示;非連通圖L6∪C8的優美標號如圖5，如圖6所示; 非連通圖L6∪C12的優美標號如圖7、圖8所示; 非連通圖L6∪C16的優美標號如圖9、圖10所示。

圖3 圖L6UC4的交錯標號

圖4 圖L6UC4的交錯標號

圖5 圖L6UC8的交錯標號

圖6 圖L6UC8的優美標號

圖7 圖L6UC12的優美標號

圖8 圖L6UC12的優美標號

圖9 圖L6UC16的優美標號

圖10 圖L6UC16的優美標號

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

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

[3]吳躍生.圖G∪T⊙K1的優美性[J].東北師大學報:自然科學版,2014,46(1):14-16.

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

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

[8]吳躍生, 王廣富，徐保根. 關于C4h+1⊙K1的(Gr1,Gr2,…,Gr4h+1,Gr4h+2)-冠的優美性[J].山東大學學報：理學版, 2013，48(4)：25-27.

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

[10]吳躍生, 王廣富，徐保根.非連通圖C2n+1∪Gn-1的優美性[J].華東交通大學學報, 2012,29(6):26-29.

[11]吳躍生.非連通圖G+e∪Hk-1的優美性[J].吉首大學學報:自然科學版,2014,35(2):3-5.

[12]吳躍生.非連通圖C4m-1∪G的優美標號[J].吉首大學學報:自然科學版,2014,35(3):1-3.

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

[14]吳躍生.非連通圖D2,8∪G的優美標號[J].西華師范大學學報:自然科學版,2014:35(1):4-6.

[15]吳躍生.非連通圖2C4(3m-1)∪C8m-1∪G的優美標號[J].唐山學院學報,2014,27(3);12-14.

[16]吳躍生非連通圖C5⊙K1∪G的優美性[J]. 汕頭大學學報:自然科學版，2014,29(3):1-4.

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

[18]吳躍生.非連通圖C4m-1∪C12m-8∪G的優美性[J].沈陽大學學報，2014,26(4);34-337.

[19]吳躍生,王廣富,徐保根. 非連通圖C4(m,0,0,0)∪G的優美性[J].河南師范大學:自然科學版,2014,42(3):23-26.

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

(編校：葉超)

TheGracefulLabelingoftheUnconnectedGraphL6∪G

WU Yue-sheng

(SchoolofScience,EastChinaJiaotongUniversity,NanChang330013China)

The gracefulness of the unconnected graphL6∪Gis discussed. Four sufficient conditions are given for the gracefulness of unconnected graphL6∪G.

graceful graph; alternating graph ; unconnected graph; graceful labeling; ladder graph

2014-05-09

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

吳躍生(1959—)，男，副教授，碩士，主要研究方向為圖論。

O157.5

：A

：1673-159X(2015)02-0030-6

10.3969/j.issn.1673-159X.2015.02.006