吴 跃 生

(华东交通大学 理学院, 江西 南昌　330013)



非连通图D2,4∪G的优美标号

吴 跃 生

(华东交通大学 理学院, 江西 南昌330013)

摘要:讨论了非连通图D2,4∪G的优美性,给出了非连通图D2,4∪G是优美图的六个充分条件.证明了非连通图D2,4∪G(k)+a(a=2,3,4,5,6,7)都是优美的.

关键词:优美图; 交错图; 非连通图; 优美标号

记号V(G)和E(G)分别表示图G的顶点集和边集,m和n均为非负整数,且满足0≤m

图的优美标号问题是组合数学中一个热门课题[1-13].文献[4-13]研究了非连通图的优美性,文献[4]研究了非连通图C4m∪G的优美性;文献[6-8]研究了非连通图C4m-1∪G的优美性;文献[9-10]分别研究了非流通图D2,6∪G和非流通图D2,8∪G的优美标号;文献[11-13]研究了非连通图C4m-1∪C12m-8∪G的优美性.

1相关概念

定义1[1]对于一个图G=(V,E),称G是优美图,θ是G的一组优美标号是指:如果存在一个单射θ: V(G)→[0, |E(G)|]使得对所有边e=uv∈E(G),由θ′(e)=|θ(u)-θ(v)|导出的E(G)→[1,|E(G)|]是一个双射.

把任意m个圈Cn的恰有一个公共点所组成的图记作Dm,n[1].

D2,4存在特征为2,且 缺4和7标号值的交错标号,如图1所示,为方便记,把如图1所示的标号记为:(1:8,0,6;5,2,3)

图1　图D2,4的交错标号

本文讨论了非连通图D2,4∪G的优美性.

2主要结果及其证明

定理1当2≤k+2≤|E(G(k)+2)|)时,非连通图D2,4∪G(k)+2存在下列标号:

(1) 特征为k+4且缺k+1和k+6标号值的交错标号;

(2) 特征为k+3且缺k+6和k+8标号值的交错标号;

(3) 缺k+3和k+7标号值的优美标号;

(4) 缺k+1和k+5标号值的优美标号.

图2　图D2,4

非连通图D2,4∪G(k)+2的各种顶点标号θ定义为

下面证明第一种标号θ是非连通图D2,4∪G(k)+2的优美标号.

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

θ:V(D2,4)→[k+2,k+10]-{k+6,k+9}是双射;

容易验证:θ: V(D2,4∪G(k)+2)→[0, q+8]-{k+1,k+6}是单射.

(2) θ′(v1v2)=|θ(v1)-θ(v2)|=6,θ′(v2v3)=|θ(v2)-θ(v3)|=5,θ′(v1v4)=|θ(v1)-θ(v4)|=8,

θ′(v3v4)=|θ(v3)-θ(v4)|=7,θ′(v3v5)=|θ(v3)-θ(v5)|=4,θ′(v5v6)=|θ(v5)-θ(v6)|=3,

θ′(v3v7)=|θ(v3)-θ(v7)|=2,θ′(v6v7)=|θ(v6)-θ(v7)|=1,

θ′:E(D2,4)→[1,8]是双射;

θ′:E(G(k)+2)→[9,q+8]是双射.

θ′:E(D2,4∪G(k)+2)→[1, q+8]是一一对应.

由(1)和(2)可知第一种标号θ就是非连通图D2,4∪G(k)+2的缺k+1和k+6标号值的优……