非连通图的优美标号
2013-10-28吴跃生王广富
吴跃生，王广富
*吴跃生，王广富
(华东交通大学基础科学学院，江西 南昌 330013)
讨论了非连通图12(1,0,2,0,…,6,0)∪F,4的优美性，证明了a,k,r(=1,2,…,6)，为任意自然数，且当5=6=0，= 3，6=，5≥ 2-，=4；6≥ 4，= 5时，非连通图12(1,0,2,0,…,6,0)∪F,4是交错图。其中12(1,0,2,0,…,6,0)∪F,4表示圈12的(1,0,2,0,…,6,0)-冠，把顺序有一个公共点的个4的连通并图记作F,4。
优美图；非连通图；平衡二分图
1 引言与概念
图的优美标号问题是组合数学中一个热门课题[1- 18]。
显然，若为的平衡标号，则是边导出标号为1的边的两个端点中标号较小的顶点的标号。
把顺序有一个公共点的个4的连通并图记作F,4[1]。
文[3-6]研究了若干优美图的冠图的优美性，文[3]已经指出：12(1,0,2,0,…,6,0)是优美图，文[7-18] 研究了一些非连通并图的优美性。本文讨论了非连通图12(1,0,2,0,…,6,0) ∪F,4的优美性。
2 主要结果及其证明
图1 图Fm,4
定义非连通图
的顶点标号为：
下面证明
：(3,4)→[7, 17] ∪{1}是单射;
容易验证：
容易验证：
例1 根据定理1，非连通图
的缺标号值6的特征为10交错标号，如图2所示。
定义非连通图
的顶点标号为：
例2 根据定理2，非连通图
缺标号值6的特征为11交错标号如图3-5所示。
图3 F4,4∪的交错标号
图4 F4,4∪的交错标号
图5 F4,4∪的交错标号
定义非连通图
的顶点标号为：
例3 根据定理3，非连通图
缺标号值6的特征为12交错标号如图6-7所示。
图6 的交错标号
[1] 马杰克.优美图[M]. 北京:北京大学出版社,1991.
[2] 杨显文.关于C4m蛇的优美性[J].工程数学学报，1995,12(4):108-112.
[3] Prabhahar Pradhan, Ajay Kumar, Debdas Mishra.On Gracefulness of Graphs Obtained from Hairy Cycles[J]. Journal of Combinatorics, Information & System Sciences ,2010, 35 (3-4):471-480.
[4] 吴跃生.关于圈C4h的(1,2,…,4h)-冠的优美性[J].华东交通大学学报,2011,28(1):77-80.
[5] 吴跃生, 李咏秋. 关于圈C4h+3的(1,2,…,4h+3)-冠的优美性[J].吉首大学学报:自然科学版,2011,32(6):1-4.
[6] 吴跃生, 王广富. 关于C4h+1⊙1的(1,2,…,4h+1,4h+2)-冠的优美性[J].山东大学学报,2013, 48(4):25-27.
[7] 吴跃生. 关于圈C4h+3的(1,2,…,4h+3)-冠的优美性[J].吉首大学学报:自然科学版,2013,34(4): 1-6.
[9] 吴跃生.关于图P6k+53∪Pn3的优美性[J]. 吉首大学学报:自然科学版,2012,33(3):4-7.
[10] 吴跃生.图C7(1,2,3, ,4,5,0,0)∪St(m )的优美性[J]. 吉首大学学报:自然科学版,2012,33(5):9-1.
[11] 吴跃生, 王广富, 徐保根. 非连通图C2n+1∪G-1的优美性[J].华东交通大学学报, 2012,29(6):26-29.
[13] 魏丽侠，张昆龙.几类并图的优美标号[J].中山大学学报:自然科学版,2008,47( 3):10-13.
[14] 蔡华，魏丽侠，吕显瑞. 非连通图(1∨P) ∪G和(1∨P) ∪(3∨K)及W∪()的优美性[J].吉林大学学报:理学版,2007, 45( 4):539-543.
[15] 蔡华.几类非连通图的优美性[D]. 长春：吉林大学,2007.
[16] 张家娟，郭珠霞，周向前,等.优美图的一些性质[J].数学的实践与认识, 2012, 42(13):197-201.
[18] Gallian J A. A Dynamic Survey of Graph Labeling[J]. The Electronic Journal of Combinatorics，2012,19:DS6.
The graceful labeling of the unconnected graph12(1,0,2,0,…,6,0)∪F,4
*WU Yue-sheng，WANG Guang-fu
(School of Basic Science, East China Jiaotong University, Nanchang, Jiangxi 330013, China)
The gracefulness of the unconnected graph12(1,0,2,0,…,6,0)∪F,4is discussed. Furthermore, we prove the following results: For any natural number a,k,r(=1,2,…,6)，if5=6=0，= 3，6=，5≥ 2-，=4；6≥ 4，= 5, then the unconnected graphs12(1,0,2,0,…,6,0)∪F,4are balanced bipartite graph.
graceful graph; unconnected graph; balanced bipartite graph
O159.1
A
10.3969/j.issn.1674-8085.2013.06.001
1674-8085(2013)06-0001-05
2013-09-22；
2013-10-12
国家自然科学基金项目(11261019，11361024) ; 江西省自然科学基金项目(20114BAB201010)
*吴跃生(1959-)，男，江西瑞金人，副教授，硕士，主要从事图论研究(E-mail:616100567@qq.com);
王广富(1976-)，男，山东荷泽人，副教授，博士，主要从事图论研究(E-mail:wgfmath@126.com).
