非连通图的优美标号

吴跃生，王广富

*吴跃生，王广富

(华东交通大学基础科学学院，江西 南昌 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].吉首大……