吴跃生

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



三探非连通图C4m-1∪G的优美标号

吴跃生

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

讨论了非连通图C4m-1∪G的优美性，给出了非连通图C4m-1∪G是优美图的2个充分条件.

优美图;交错图；非连通图;优美标号

1 相关定义

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

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

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

与圈有关的图的优美性是人们研究的一个重点.Rosa A[1]已经证明:圈C4n和圈C4n+3都是优美的.将由m个互不相交的n回路Cn所组成的图记作mCn.Anton Kotzig猜想[2]:对每一对自然数j和k，jC4k是优美图.这个猜想没有得到证明或否定.有许多论文讨论了若干圈的非连通并图的优美性.

文献[13]讨论了非连通图C4m-1∪G的优美性，给出了非连通图C4m-1∪G是优美图的2个充分条件：对任意正整数m，若图G是特征为k且缺k+3m-1标号值的交错图(3m-1≤k+3m-1≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+1的优美标号；对任意正整数m，若图G是特征为k且缺k+m+1标号值的交错图(m+1≤k+m+1≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+1的优美标号.证明了:对任意正整数m，非连通图C4m-1∪C4m存在缺标号值2m的优美标号;对任意正整数m，非连通图C4m-1∪C12m-8存在缺标号值6m-4的优美标号.

文献[17]再讨论了非连通图C4m-1∪G的优美性，给出了非连通图C4m-1∪G是优美图的2个充分条件：对任意正整数m，若图G是特征为k且缺k+3m-2标号值的交错图(3m-2≤k+3m-2≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+4m-1的优美标号；……