非连通图C12(r1,0,r2,0,r3,0,…,0)∪G的优美标号

吴跃生，王广富

非连通图12(1,0,2,0,3,0,…,0)∪的优美标号

*吴跃生，王广富

(华东交通大学基础科学学院，江西，南昌 330013)

讨论了非连通图12(1,0,2,0,3,0,…,0)∪的优美性，给出了非连通图12(1,0,2,0,3,0,…,0)∪是优美图的一个充分条件。

优美图；非连通图；平衡二分图

1 引言与概念

图的优美标号问题是组合数学中一个热门课题[1-10]。

成立，则称为的平衡标号(或称有平衡标号)，且称为的特征。图称为平衡二分图（balanced bipartite graph）。

显然，若为的平衡标号，则是边导出标号为1的边的两个端点中标号较小的顶点的标号。

定义5[3-4]()={1,2,…,n}的每个顶点i都粘接了r条悬挂边(r为自然数，=1, 2,…,)所得到的图，称为图的1,2,…,r)-冠，简记为1,2,…,r)。特别地，当1=2=… =r=时，称为图的-冠。图的0-冠就是图。

文[1]给出了图12的交错标号。本文讨论了非连通图12(1,0,2,0,3,0,…,0)∪的优美性。

2 主要结果及其证明

令={13,5,7,9,11}∪1，={24,6, u, u10,12}∪{yi,j|1,2,3,j= r}∪1

则有

引理1[3]对任意自然数1，2，3，4,12(1,02,03,0,4, 00,000)) 存在特征值为5且缺标号值9的交错标号。

令={13,5, u u9,11},={24,6, u u10,12}∪{y2i-1,j|1,2,341,2,…,r}则有

由定理和引理1，有

推论2对任意自然数r(=1,2,…,7),则非连通图12(1,0,2,0,3,0,…,0)∪12(4,05,06,0,7,00,000)存在缺标号值6的特征为12交错标号。

引理2对任意自然数1,4(1,22,2)存在特征值为5且缺标号值9的交错标号。

令={1，3，2,1，2,2，4,1，4,2}，={24,}∪ {1, j|12…,1}∪{3,1,3,2}则有

由引理2和定理，有

推论3对任意自然数r(=1,2,3,4)非连通图12(1,0,2,0,3,0,…,0)∪4(4,22,2 )存在缺标号值6的特征为12交错标号。

引理3[1]对任意自然数，, 当≥4，≥2时，完备二分图K存在特征为1且缺m+3标号值的交错标号。

证设完备二分图K的顶点二分划为1，2，1={1,2,…,m},2={1,2,…,u}。

容易验证：对任意自然数，,当≥4，≥2时，完备二分图K存在特征为1且缺m+3标号值的交错标号。

由引理3和定理，有

推论4 对任意自然数r(=1,2,3),,,当≥4，≥2时, 非连通图12(1,0,2,0,3,0,…,0)∪K存在缺标号值的特征为4交错标号。

引理4 对任意自然数r(=1,2)，当2≥1时，非连通图8(1,0,2,0,2,0,2,0)存在缺标号值7的特征为3交错标号。

Ⅰ 当2=1时

令={13,5, u},

={24,6, u}∪{y1,j|1,2,…1}∪

{y2,1, y3,1,y4,1}

则有

Ⅱ 当2≥2时

令={13,5, u},={24,6, u}∪

{1,j1,2,1}∪{y2, 3,4,1,2,…,2}

则有

由引理4和定理，有

推论5 对任意自然数r(=1,2,3,4,5), r≥1,非连通图12(1,0,2,0,3,0,…,0)∪8(4,05,0,5,0,5,0)存在缺标号值4的特征为10交错标号。

图1 ∪C12(1,0,2,0,3,0,4,0,0,0,0,0)的交错标号

图2 C12(1,0,3,0,2,0,0,…,0) ∪C12(1,0,2,0,3,0,4,0,0,0,0,0)的交错标号

图3 C12(1,0,3,0,2,0,0,…,0) ∪C4(8,2,2,2)的交错标号

图4 C12(2,0, 2,0, 2,0,0,…,0) ∪K42的交错标号

图5 C12(3,0, 0,0, 3,0,0,…,0) ∪C8(6,0, 1,0, 1,0,1,0)的交错标号

图612(1,0, 4,0, 2,0,0,…,0) ∪8(5,0, 2,0, 2,0,2,0)的交错标号

Fig.6 The altemating labeling of12(1,0, 4,0, 2,0,0,…,0) ∪8(5,0, 2,0, 2,0,2,0)

[1] 马杰克.优美图[M]. 北京:北京大学出版社,1991.

[2] 杨显文.关于C4m蛇的优美性[J].工程数学学报，1995,12(4):108-112.

[3] 吴跃生.关于圈C4h的(1,2,…,4h)-冠的优美性[J].华东交通大学学报,2011,28(1):77-80.

[4] 吴跃生, 李咏秋. 关于圈C4h+3的(1,2,…,4h+3)-冠的优美性[J].吉首大学学报:自然科学版,2011,32(6):1-4.

[5] 吴跃生.关于图6k+53∪P3的优美性[J] 吉首大学学报:自然科学版,2012,33(3):4-7.

[7] 吴跃生.图C7(1,2,3, ,4,5,0,0)∪St(m )的优美性[J]. 吉首大学学报:自然科学版,2012,33(5):9-11.

[8] 吴跃生, 王广富，徐保根. 关于C4h+1⊙1的(1,2,…,4h+1,4h+2)-冠的优美性[J].山东大学学报, 2013,48(4):25-27.

[9] 吴跃生. 关于圈C4h+3的(1,2,…,4h+3)-冠的优美性[J].吉首大学学报:自然科学版,2013,34(4): 1-6.

[10] 吴跃生,王广富,徐保根.非连通图C2n+1∪G-1的优美性[J].华东交通大学学报, 2012,29(6):26-29.

The graceful labeling of the unconnected graph12(1,02,0,r,0,…,0)∪

*WU Yue-sheng WANG Guang-fu

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

The gracefulness of the Graph121020300∪are discussed. One sufficient conditionsis given for the gracefulness of unconnected graph121020300∪

graceful graph;unconnected graph; balanced bipartite graph

O159.1

A

10.3969/j.issn.1674-8085.2014.02.001

1674-8085(2014)02-0001-06

2013-12-09；

2014-01-11

国家自然科学基金项目(11261019,11361024)；江西省自然科学基金项目(20114BAB201010)

*吴跃生(1959-)，男，江西瑞金人，副教授，硕士，主要从事图论研究(E-mail: 616100567@qq.com);

王广富(1976-)，男，山东荷泽人，副教授，博士，主要从事图论研究(E-mail:wgfmath@126.com).