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

·基礎(chǔ)學(xué)科·

非連通圖L6∪G的優(yōu)美標(biāo)號(hào)

吳 躍 生

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

討論非連通圖L6∪G的優(yōu)美性，給出了非連通圖L6∪G是優(yōu)美圖的4個(gè)充分條件。

優(yōu)美圖;交錯(cuò)圖；非連通圖;優(yōu)美標(biāo)號(hào);梯圖

1 引言與概念

圖的優(yōu)美標(biāo)號(hào)問題是組合數(shù)學(xué)中一個(gè)熱門課題[1-20]。

本文討論了非連通圖L6∪G的優(yōu)美性。

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

梯圖L6存在如圖1所示的優(yōu)美標(biāo)號(hào)。

圖1 梯圖L6的優(yōu)美標(biāo)號(hào)

梯圖L6存在如圖1所示的特征為2且缺標(biāo)號(hào)值4，6的交錯(cuò)標(biāo)號(hào)。

2 主要結(jié)果及其證明

圖2 圖L6

定義L6∪Gk+2的頂點(diǎn)標(biāo)號(hào)θ為：

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

下面證明θ是非連通圖L6∪Gk+2的優(yōu)美標(biāo)號(hào)。

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標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

則有

所以，θ就是非連通圖L6∪Gk+2的特征為k+4,且缺k+1和k+6標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。 證畢。

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

定義L6∪Gk+2的頂點(diǎn)標(biāo)號(hào)θ為：

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

下面證明θ是非連通圖L6∪Gk+2的優(yōu)美標(biāo)號(hào)。

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標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

則有

所以，θ就是非連通圖L6∪Gk+2的特征為k+4,且缺k+1和k+7標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。 證畢。

定義L6∪Gk+3的頂點(diǎn)標(biāo)號(hào)θ為：

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

下面證明θ是非連通圖L6∪Gk+3的優(yōu)美標(biāo)號(hào)。

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標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

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

則有

所以，θ就是非連通圖L6∪Gk+3的特征為k+5,且缺k+1和k+2標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。 證畢。

定義L6∪Gk+3的頂點(diǎn)標(biāo)號(hào)θ為：

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

下面證明θ是非連通圖L6∪Gk+3的優(yōu)美標(biāo)號(hào)。

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標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

定義L6∪Gk+4的頂點(diǎn)標(biāo)號(hào)θ為：

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

下面證明θ是非連通圖L6∪Gk+4的優(yōu)美標(biāo)號(hào)。

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標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。證畢。

定義L6∪Gk+4的頂點(diǎn)標(biāo)號(hào)θ為：

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

下面證明θ是非連通圖L6∪Gk+4的優(yōu)美標(biāo)號(hào)。

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標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。證畢。

定義L6∪Gk+5的頂點(diǎn)標(biāo)號(hào)θ為：

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

下面證明θ是非連通圖L6∪Gk+5的優(yōu)美標(biāo)號(hào)。

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標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。證畢。

定義L6∪Gk+5的頂點(diǎn)標(biāo)號(hào)θ為：

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

下面證明θ是非連通圖L6∪Gk+5的優(yōu)美標(biāo)號(hào)。

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標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。證畢。

引理1[1]對(duì)任意正整數(shù)n，設(shè)C4n是有4n個(gè)頂點(diǎn)的圈，則C4n存在特征為2n-1,且缺3n的交錯(cuò)標(biāo)號(hào)。

證記圈C4n上的頂點(diǎn)依次為v1,v2,…,v4n，定義圈C4n的頂點(diǎn)標(biāo)號(hào)θ為

容易驗(yàn)證，θ就是圈C4n的特征為2n-1,且缺3n的交錯(cuò)標(biāo)號(hào)。

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

推論2非連通圖L6∪C4存在特征為5且缺2和7標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

由定理2和引理1有

推論3非連通圖L6∪C4存在特征為5且缺2和8標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

由定理3和引理1有

推論4非連通圖L6∪C8存在特征為8且缺4和5標(biāo)號(hào)值的交錯(cuò)標(biāo)號(hào)。

由定理4和引理1有

推論5非連通圖L6∪C8存在缺9和10標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

由定理5和引理1有

推論6非連通圖L6∪C12存在缺7和12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

由定理6和引理1有

推論7非連通圖L6∪C12存在缺6和12標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

由定理7和引理1有

推論8非連通圖L6∪C16存在缺8和10標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

由定理8和引理1有

推論9非連通圖L6∪C16存在缺8和9標(biāo)號(hào)值的優(yōu)美標(biāo)號(hào)。

例非連通圖L6∪C4的交錯(cuò)標(biāo)號(hào)如圖3、圖4所示;非連通圖L6∪C8的優(yōu)美標(biāo)號(hào)如圖5，如圖6所示; 非連通圖L6∪C12的優(yōu)美標(biāo)號(hào)如圖7、圖8所示; 非連通圖L6∪C16的優(yōu)美標(biāo)號(hào)如圖9、圖10所示。

圖3 圖L6UC4的交錯(cuò)標(biāo)號(hào)

圖4 圖L6UC4的交錯(cuò)標(biāo)號(hào)

圖5 圖L6UC8的交錯(cuò)標(biāo)號(hào)

圖6 圖L6UC8的優(yōu)美標(biāo)號(hào)

圖7 圖L6UC12的優(yōu)美標(biāo)號(hào)

圖8 圖L6UC12的優(yōu)美標(biāo)號(hào)

圖9 圖L6UC16的優(yōu)美標(biāo)號(hào)

圖10 圖L6UC16的優(yōu)美標(biāo)號(hào)

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

[2]楊顯文.關(guān)于C4m蛇的優(yōu)美性[J].工程數(shù)學(xué)學(xué)報(bào)，1995,12(4):108-112.

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

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

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

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

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

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

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

[12]吳躍生.非連通圖C4m-1∪G的優(yōu)美標(biāo)號(hào)[J].吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2014,35(3):1-3.

[13]賈慧羨,左大偉.與扇圖相關(guān)的2類圖的超邊優(yōu)美標(biāo)號(hào)[J]. 吉首大學(xué)學(xué)報(bào):自然科學(xué)版,2014,35(2):6-9.

[14]吳躍生.非連通圖D2,8∪G的優(yōu)美標(biāo)號(hào)[J].西華師范大學(xué)學(xué)報(bào):自然科學(xué)版,2014:35(1):4-6.

[15]吳躍生.非連通圖2C4(3m-1)∪C8m-1∪G的優(yōu)美標(biāo)號(hào)[J].唐山學(xué)院學(xué)報(bào),2014,27(3);12-14.

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

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

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

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

[20]吳躍生.再探非連通圖C(4m-1)∪G的優(yōu)美標(biāo)號(hào)[J].吉首大學(xué)學(xué)報(bào)：自然科學(xué)版,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

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

吳躍生(1959—)，男，副教授，碩士，主要研究方向?yàn)閳D論。

O157.5

：A

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

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