非连通图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