非连通图G+e∪Hk-1的优美性*

2014-09-05 09:23吴跃生

吉首大学学报（自然科学版） 2014年2期

关键词：下结论条边标号

吴跃生

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

非连通图G+e∪Hk-1的优美性*

吴跃生

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

证明了当k≥2时，非连通图G+e∪Hk-1是优美图,其中G是特征为k的平衡二分图，Hk-1是任意一个k-1条边的优美图.

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

1 相关定义

文中所讨论的图均为无向简单图，V(G)和E(G)分别表示图G的顶点集和边集.为了简单起见，将一个有p个顶点q条边的图记为(p,q)-图.记号[m,n]表示整数集合{m，m+1,m+2,...，n}，其中m和n均为非负整数，且满足0≤m

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

定义2[1]设f为G的一个优美标号，若存在一个正整数k，使得对任意的uv∈E(G)，有f(u)>k≥f(v)或f(u)≤k

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

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

定义5[1]v1,v2是图G的2个非邻接的顶点，则e=v1v2∉E(G).用G+e表示顶点集为V(G)，且边集为E(G)∪{e}的图，即V(G+e)=V(G),E(G+e)=E(G)∪{e}.

2 主要结果及其证明

再令θ3(v)=q-θ2(v),v∈V(G),则θ,θ1,θ2,θ3是图G的互不相同的4种平衡标号,其特征分别为k,q-k-1,k和q-k-1.

定理1 当k≥2时，(p,q)-图G是特征为k的平衡二分图，Hk-1是边数为k-1的优美图，则非连通图G+e∪Hk-1是优美的.

证明设V(G)划分成2个集合X,Y,θ是图G的平衡标号,且：(1)v1,v2∈X,θ(v1)=0,θ(v2)=k,即v2是平衡二分图G的二分点；(2)存在v1,v2∈Y，有|θ(v1)-θ(v2)|=k.

定义图G+e∪Hk-1的顶点标号θ1为

下面证明标号θ1是图G+e∪Hk-1的优美标号.

因此θ1是图G+e∪Hk-1的优美标号.证毕.

由引理1和定理1有如下结论：

推论1 当q-k-2≥时，(p,q)-图G是特征为k的平衡二分图，Hq-k-2是边数为q-k-2的优美图，则非连通图G+e∪Hq-k-2是优美的.

证明设(p,q)-图G的关于平衡标号θ的特征为k,θ(v1)=q，θ(v2)=k+1，令θ1(v)=q-θ(v),v∈V(G).由引理1知，θ1是(p,q)-图G的另一个平衡标号，(p,q)-图G的关于平衡标号θ的特征为q-k-1，且有θ1(v1)=0，θ1(v2)=q-k-1.由定理1知，非连通图G(v1v2)∪Hq-k-2是优美的.证毕.

在定理1中，令Hk-1=St(k-1)(St(k-1)表示有k个顶点或有k-1条边的星形树)，有如下结论：

推论2 当k≥2,(p,q)-图G是特征为k的平衡二分图时，G+e∪St(k-1)是优美图.

在定理1中，令Hk-1=Pk(Pk表示有k个顶点或有k-1条边的路)，有如下结论：

推论3 当k≥2,(p,q)-图G是特征为k的平衡二分图时,G+e∪Pk是优美图.

在定理1中，令Hk-1=Tk(Tk表示有k个顶点或有k-1条边的优美树)，有如下结论：

推论4 当k≥2,(p,q)-图G是特征为k的平衡二分图时,G+e∪Tk是优美图.

在定理1中，令Hk-1=Ck-1,k=4n,有如下结论：

推论5 当n≥1,(p,q)-图G是特征为4n的平衡二分图时，G+e∪C4n-1是优美图.

在定理1中，令Hk-1=Ck-1,k=4n+1,有如下结论：

推论6 当n≥1,(p,q)-图G是特征为4n+1的平衡二分图时,G+e∪C4n是优美图.

在定理1中，令Hk-1=Ck-2⊙K1,当k≥5时,Ck-2⊙K1是优美图，所以有如下结论：