非连通图D4∪G的优美标号

2014-07-24吴跃生

盐城工学院学报（自然科学版） 2014年4期

关键词：标号顶点学报

吴跃生

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

非连通图D4∪G的优美标号

吴跃生

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

讨论了非连通图D4∪G的优美性，给出了非连通图D4∪G是优美图的3个充分条件。

优美图;交错图；非连通图;优美标号;荷兰m-风车

1 引言与概念

本文所讨论的图均为无向简单图，V(G)和E(G)分别表示图G的顶点集和边集，记号[m,n]表示整数集合{m,m+1,…,n}，其中m和n均为非负整数，且满足0≤m

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

定义1[1]由m个完备图K3的恰有一个公共点所构成的图成为荷兰m-风车(Dutchm-wind-mill)，记作Dm[1]。

文献[1]已指出：Dm是优美图的充要条件为：m=0,1(mod4)。

本文讨论非连通图D4∪G的优美性。

定义3[1]设f为G的一个优美标号，如果存在一个正整数k，使得对任意的uv∈E(G)有

成立，则称f为G的平衡标号(或称G有平衡标号f)，且称k为f的特征。图G称为平衡二分图(balancedbipartitegraph)。

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

定义4[1]在平衡二分图G中，设其优美标号θ的特征为k，并且θ(u0)=k，θ(v0)=k+1，则称u0为G的二分点，v0为G的对偶二分点。

2 主要结果及其证明

定理 1 如果图G是特征为k且缺k+2标号值的交错图(2≤k+2≤|E(G)|)，则非连通图D4∪G存在缺k+1、k+7、k+8和k+9标号值的优美标号。

图1 荷兰风车图D4Fig.1 Dutch wind-mill D4

定义D4∪G的顶点标号θ为：

θ(v1)=k+2，θ(v2)=k+6，θ(v3)=k+12，

θ(v4)=k+3，θ(v5)=k+14,θ(v6)=k+5，

θ(v7)=k+10，θ(v8)=k+4，θ(v9)=k+11，

下面证明θ是非连通图D4∪G的优美标号。

(1)θ:X→[0, k]是单射(或双射);θ:Y→[k+13,q+12]-{k+14}是单射(或双射);

θ:V(D4)→[k+2,k+12]∪{k+14}-{k+7,k+8,k+9}是双射;

容易验证：θ:V(D4∪G)→[0,q+12]-{k+1,k+7,k+8,k+9}是单射(或双射)。

(2)θ′(v1v2)=|θ(v1)-θ(v2)|=4,

θ′(v1v3)=10,θ′(v2v3)=6, θ′(v1v4)=1,

θ′(v1v5)=12,θ′(v4v5)=11,θ′(v6v1)=3,

θ′(v7v1)=8, θ′(v6v7)=5, θ′(v8v1)=2,

θ′(v9v1)=9, θ′(v8v9)=7。

θ′:E(D4)→[1,12]是双射；

θ′:E(G)→[13,q+12]是双射。

θ′：E(D4∪G)→[1,q+12]是一一对应。

由(1)和(2)可知,θ就是非连通图D4∪G的缺k+1、k+7、k+8和k+9标号值的优美标号。证毕。

定理 2 如果图G是特征为k且缺k+10标号值的交错图(10≤k+10≤|E(G)|)，则非连通图D4∪G存在缺k+4、k+5、k+6和k+12标号值的优美标号。

定义D4∪G的顶点标号θ为：

θ(v1)=k+11，θ(v2)=k+1， θ(v3)=k+7，

θ(v4)=k+10，θ(v5)=k+22,θ(v6)=k+8，

θ(v7)=k+3， θ(v8)=k+9，θ(v9)=k+2，

下面证明θ是非连通图D4∪G的优美标号。

(1)θ:X→[0, k]是单射(或双射);θ:Y→[k+13,q+12]-{k+22}是单射(或双射);

θ:V(D4)→[k+1,k+11]∪{k+22}-{k+4,k+5,k+6}是双射;

容易验证：θ: V(D4∪G)→[0,q+12]-{k+4,k+5,k+6,k+12}是单射(或双射)。

(2)θ′(v1v2)=|θ(v1)-θ(v2)|=10,

θ′(v1v3)=4, θ′(v2v3)=6,θ′(v1v4)=1,

θ′(v1v5)=11,θ′(v4v5)=12,θ′(v6v1)=3,

θ′(v7v1)=8, θ′(v6v7)=5,θ′(v8v1)=2,

θ′(v9v1)=9, θ′(v8v9)=7。

θ:E(D4)→[1,12]是双射；

θ′:E(G)→[13,q+12]是双射。

θ′：E(D4∪G)→[1,q+12]是一一对应。

由(1)和(2)可知，θ就是非连通图D4∪G的缺k+4、k+5、k+6和k+12标号值的优美标号。证毕。

定理 3 如果图G是特征为k且缺k+11标号值的交错图(11≤k+11≤|E(G)|)，则非连通图D4∪G存在缺k+1、k+5、k+6和k+7标号值的优美标号。

定义D4∪G的顶点标号θ为：

θ(v1)=k+12，θ(v2)=k+2，θ(v3)=k+8，

θ(v4)=k+11，θ(v5)=k+23,θ(v6)=k+9，

θ(v7)=k+4，θ(v8)=k+10，θ(v9)=k+3，

下面证明θ是非连通图D4∪G的优美标号。

(1)θ:X→[0, k]是单射(或双射);θ:Y→[k+13,q+12]-{k+23}是单射(或双射);

θ:V(D4)→[k+2,k+12]∪{k+23}-{k+5,k+6,k+7}是双射;

容易验证：θ:V(D4∪G)→[0,q+12]-{k+1,k+5,k+6,k+7}是单射(或双射)。

(2)θ′(v1v2)=|θ(v1)-θ(v2)|=10,

θ′(v1v3)=4,θ′(v2v3)=6, θ′(v1v4)=1,

θ′(v1v5)=11,θ′(v4v5)=12,θ′(v6v1)=3,

θ′(v7v1)=8,θ′(v6v7)=5,θ′(v8v1)=2,

θ′(v9v1)=9,θ′(v8v9)=7。

θ′:E(D4)→[1,12]是双射；

θ′: E(G)→[13,q+12]是双射。

θ′：E(D4∪G)→[1,q+12]是一一对应。

由(1)和(2)可知，θ就是非连通图D4∪G的缺k+1、k+5、k+6和k+7标号值的优美标号。证毕。

引理1 对任意正整数n，设C4n是有4n个顶点的圈，则C4n存在特征为2n-1,且缺3n的交错标号。

证明记圈C4n上的顶点依次为v1，v2,…,v4n,定义圈C4n的顶点标号θ为：

容易验证，θ就是圈C4n的特征为2n-1,且缺3n的交错标号。

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

推论1 非连通图D4∪C4存在缺2、8、9和11标号值的优美标号。

非连通图D4∪C4的优美标号如图2所示。

图2 非连通图D4∪C4的优美标号Fig.2 The graceful labeling of the graph D4∪C4

由定理2和引理1有：

推论2 非连通图D4∪C36存在缺21、22、23和29标号值的优美标号。

非连通图D4∪C36中D4的优美标号如图3所示。非连通图D4∪C36中C36的优美标号为:0、48、

图3 非连通图D4∪C36中D4的优美标号Fig.3 The graceful labeling of the graph D4of the graph D4∪C36

1、47、2、46、3、45、4、44、5、43、6、42、7、41、8、40、9、38、10、37、11、36、12、35、13、34、14、33、15、32、16、31、17、30。

由定理3和引理1有：

推论3 非连通图D4∪C40存在缺20、24、25和26标号值的优美标号。

非连通图D4∪C40中D4的优美标号如图4所示。非连通图D4∪C40中C40的优美标号为:0、52、1、51、2、50、3、49、4、48、5、47、6、46、7、45、8、44、9、43、10、41、11、40、12、39、13、38、14、37、15、36、16、35、17、34、18、33、19、32。