非连通图（P1∨Pm）∪C4n∪P2的优美性

吴跃生，王广富，徐保根

（华东交通大学基础科学学院，江西南昌330013）

1 引言与预备知识

优美图集广泛的应用性和趣味性于一身，因而优美图的研究是图论中较为活跃的课题之一[1-20].许多学者对非连通图的优美性进行了研究[4-18].本文考虑非连通图（P1∨Pm）∪C4n∪P2的优美性.

本文所讨论的图均为无向简单图，V（G）和E（G）分别表示图G的顶点集和边集，未说明的符号及术语均同文献[1].

定义1[1]对于一个图G=（V，E），如果存在一个单射 θ：V（G）→{0，1，2，…，|E（G）|}，使得对所有边 e=（u，v）∈E（G），由 θ′（e）=|θ（u）- θ（v）|导出的映射 E（G）→{1，2，…，|E（G）|}是双射，则称 G 是优美图，称θ是G的一组优美标号，称θ′为G的边上的由θ导出的诱导值.

定义2[1]若一个图G的顶点集V（G）能分成2个非空子集X和Y，使得X∪Y=V（G），X∩Y且G的每条边的端点分别在X和Y中，则称G为二分图，记作 G=（X，Y；E），二分划记为（X，Y）；如果G是优美的，则称为优美二分图.

定义3[3]设G是一个优美二分图，其优美标号为θ，将V（G）划分成2个集合X、Y，如果则称θ是G的交错标号.称G是在交错标号θ下的交错图.

定义4[1]设θ为G的一个优美标号，如果存在正整数 k，使得对任意的（u，v）∈E（G），有

成立，则称θ为G的平衡标号（或称G有平衡标号θ），且称k为θ的特征.图G称为平衡二分图.

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

由定义3和定义4知：平衡图与交错图等价，平衡图的平衡标号θ的特征

定义5[1]设图G1和G2不相交，在G1∪G2中，把G1的每个顶点和G2的每个顶点连接起来所得到的图叫做G1和G2的联图，记作G1∨G2.

2 主要结果

引理1 如果优美图G不存在a的优美值，a为自然数（1≤a≤|E（G）|-1），交错图H关于交错标号的特征为k，交错图H不存在k+1+a的优美值，则非连通图G∪H∪P2是优美图.

证明 设G的优美标号为 θ，|E（G）|=n，|E（H）|=m-1，θ1是图H的交错标号，其特征为k，（X，Y）是H的二分划v1v2，定义非连通图G∪H∪P2的标号θ2如下：

下面证明θ2是非连通图G∪H∪P2的优美标号.

（1）非连通图G∪H∪P2中G的顶点标号集合是{k+1，k+2，…，k+a}∪{k+a+2，k+a+3，…，n+k+1}的子集，G的顶点标号互不相同.

在优美标号θ下，图G边导出标号集合是{1，2，…，n}，可知在标号θ2下，图G边导出标号集合还是{1，2，…，n}.

（2）非连通图G∪H∪P2中H的顶点标号集合是{0，1，…，k}∪{k+2+n，k+3+n，…，k+1+a+n}∪{k+3+a+n，k+4+a+n，…，n+m} 的子集，边导出标号集合是{n+2，n+3，…，m+n}.

（3）非连通图G∪H∪P2中P2的顶点标号集合是{k+1+a，k+1+a+n+1}，边导出标号集合是{n+1}.

由（1）、（2）和（3）可知 θ2是非连通图 G∪H∪P2的优美标号.证毕.

引理2[1]设θ是图G的一个优美标号，对任意的顶点 v∈V（G），定义 θ：θ（v）=|E（G）|- θ（v），v∈V（G），则θ是一个异于θ的优美标号.

引理3 设Pn是n个顶点的路，则P1∨Pn是优美图.

证明 记 P1和 Pn上的顶点依次为 v0和 v1，v2，…，vn，定义P1∨Pn的第1种顶点标号θ为：

θ（v0）=0，θ（v2i）=2i-1，i=1，2，…，n/2，n为偶数；i=1，2，…，（n-1）/2，n为奇数

θ（v2i-1）=2n-（2i-1），i=1，2，…，n/2，n 为偶数；i=1，2，…，（n+1）/2，n为奇数容易验证，θ是P1∨Pn的优美标号，且缺标号值2，4，…，2n-2.定义 θ：

由引理2知θ是一个异于θ的优美标号，且缺标号值1，3，…，2n-3.

定义P1∨Pn的第2种顶点标号θ为：

θ（v0）=2n-1，θ（v2i）=n-i，i=1，2，…，n/2，n为偶数；i=1，2，…，（n-1）/2，n为奇数

θ（v2i-1）=i-1，i=1，2，…，n/2，n 为偶数；i=1，2，…，（n+1）/2，n为奇数

容易验证，θ是P1∨Pn的优美标号，且缺标号值n，n+1，…，2n-2.定义 θ：

θ（v）=|E（P1∨Pn）|- θ（v） v∈V（P1∨Pn）

由引理2知θ是一个异于θ的优美标号，且缺标号值1，2，…，n-1.

引理4 设C4n是4n个顶点的圈，则C4n存在特征为2n-1，且缺3n的交错标号.

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

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

定理 设m，n为任意正整数，当m≥2，1≤n≤2m-2 时，非连通图（P1∨Pm）∪C4n∪P2是优美图.

证明 由引理3知，图P1∨Pm存在缺标号值为1，2，…，m-2的优美标号.由引理4知，圈C4n存在特征为2n-1，且缺3n的交错标号.注意到3n=（2n-1）+1+n，由引理 1可知，当 m≥2，1≤n≤2m-2时，非连通图（P1∨Pm）∪C4n∪P2是优美图.

例（P1∨P5）∪C4n∪P2（1≤n≤8）的第1种优美标号如下：

（P1∨P5）∪C4∪P2的优美标号：P1的标号为 11；P5上各点的标号依次为 2，10，4，8，6；C4上各点的标号依次为0，14，1，12；P2上各点的标号依次为3，13.注：（P1∨P5）的优美标号：P1的标号为 9；P5上各点的标号依次为0，8，2，6，4；C4上缺标号值3的各点的优美标号依次为0，4，1，2.

（P1∨P5）∪C12∪P2的优美标号：P1的标号为 15；P5上各点的标号依次为 6，14，8，12，10；C12上各点的标号依次为 0，22，1，21，2，20，3，18，4，17，5，16；P2上各点的标号依次为 9，19.注：（P1∨P5）的优美标号：P1的标号为9；P5上各点的标号依次为0，8，2，6，4；C12上缺标号值9的各点的优美标号依次为0，12，1，11，2，10，3，8，4，7，5，6.

（P1∨P5）∪C20∪P2的优美标号：P1的标号为 19；P5上各点的标号依次为 10，18，12，16，14；C20上各点的标号依次为 0，30，1，29，2，28，3，27，4，26，5，24，6，23，7，22，8，21，9，20；P2上各点的标号依次为 15，25.注：（P1∨P5）的优美标号：P1的标号为9；P5上各点的标号依次为 0，8，2，6，4；C20上缺标号值15的各点的优美标号依次为0，20，1，19，2，18，3，17，4，16，5，14，6，13，7，12，8，11，9，10.

（P1∨P5）∪C28∪P2的优美标号：P1的标号为 23；P5上各点的标号依次为 14，22，16，20，18；C28上各点的标号依次为 0，38，1，37，2，36，3，35，4，34，5，33，6，32，7，30，8，29，9，28，10，27，11，26，12，25，13，24；P2上各点的标号依次为 21，31.注：（P1∨P5）的优美标号：P1的标号为9；P5上各点的标号依次为 0，8，2，6，4；C28上缺标号值 21的各点的优美标号依次为 0，28，1，27，2，26，3，25，4，24，5，23，6，22，7，20，8，19，9，18，10，17，11，16，12，15，13，14.

（P1∨P5）∪C8∪P2的优美标号：P1的标号为 4；P5上各点的标号依次为13，5，11，7，9；C8上各点的标号依次为 0，18，1，17，2，15，3，14；P2上各点的标号依次为 6，16.注：（P1∨P5）的优美标号：P1的标号为 0；P5上各点的标号依次为 9，1，7，3，5；C8上缺标号值6的各点的优美标号依次为0，8，1，7，2，5，3，4.

（P1∨P5）∪C16∪P2的优美标号：P1的标号为 8；P5上各点的标号依次为17，9，15，11，13；C16上各点的标号依次为 0，26，1，25，2，24，3，23，4，21，5，20，6，19，7，18；P2上各点的标号依次为 12，22.注：（P1∨P5）的优美标号：P1的标号为0；P5上各点的标号依次为 9，1，7，3，5；C16上缺标号值 12的各点的优美标号依次为 0，16，1，15，2，14，3，13，4，11，5，10，6，9，7，8.

（P1∨P5）∪C24∪P2的优美标号：P1的标号为 12；P5上各点的标号依次为 21，13，19，15，17；C24上各点的标号依次为 0，34，1，33，2，32，3，31，4，30，5，29，6，27，7，26，8，25，9，4，10，23，11，22；P2上各点的标号依次为 18，28.注：（P1∨P5）的优美标号：P1的标号为0；P5上各点的标号依次为9，1，7，3，5；C24上缺标号值18的各点的优美标号依次为0，24，1，23，2，22，3，21，4，20，5，19，6，17，7，16，8，15，9，14，10，13，11，12.

（P1∨P5）∪C32∪P2的优美标号：P1的标号为 16；P5上各点的标号依次为 25，17，23，19，21；C32上各点的标号依次为 0，42，1，41，2，40，3，39，4，38，5，37，6，36，7，35，8，33，9，32，10，31，11，30，12，29，13，28，14，27，15，26；P2上各点的标号依次为 24，34.注：（P1∨P5）的优美标号：P1的标号为 0；P5上各点的标号依次为9，1，7，3，5；C32上缺标号值24的各点的优美标号依次为 0，32，1，31，2，30，3，29，4，28，5，27，6，26，7，25，8，23，9，22，10，21，11，20，12，19，13，18，14，17，15，16.

（P1∨P5）∪C4n∪P2（1≤n≤8）的第2种优美标号如下：

（P1∨P5）∪C4∪P2的优美标号：P1的标号为 2；P5上各点的标号依次为11，7，10，8，9；C4上各点的标号与第一种标号相同；P2上各点的标号依次为3，13.注：（P1∨P5）的优美标号：P1的标号为 0；P5上各点的标号依次为9，5，8，6，7.

（P1∨P5）∪C8∪P2的优美标号：P1的标号为 4；P5上各点的标号依次为13，9，12，10，11；C8上各点的标号与第一种标号相同；P2上各点的标号依次为6，16.注：（P1∨P5）的优美标号：P1的标号为 0；P5上各点的标号依次为 9，5，8，6，7.

（P1∨P5）∪C12∪P2的优美标号：P1的标号为 6；P5上各点的标号依次为 15，11，14，12，13；C12上各点的标号与第一种标号相同；P2上各点的标号依次为9，19.注：（P1∨P5）的优美标号：P1的标号为 0；P5上各点的标号依次为9，5，8，6，7.

（P1∨P5）∪C16∪P2的优美标号：P1的标号为 8；P5上各点的标号依次为 17，13，16，14，15；C16上各点的标号与第一种标号相同；P2上各点的标号依次为12，22.注：（P1∨P5）的优美标号：P1的标号为 0；P5上各点的标号依次为9，5，8，6，7.

（P1∨P5）∪C20∪P2的优美标号：P1的标号为 19；P5上各点的标号依次为 10，14，11，13，12；C20上各点的标号与第一种标号相同；P2上各点的标号依次为15，25.注：（P1∨P5）的优美标号：P1的标号为 9；P5上各点的标号依次为0，4，1，3，2.

（P1∨P5）∪C24∪P2的优美标号：P1的标号为 21；P5上各点的标号依次为 12，16，13，15，14；C24上各点的标号与第一种标号相同；P2上各点的标号依次为18，28.注：（P1∨P5）的优美标号：P1的标号为 9；P5上各点的标号依次为0，4，1，3，2.

（P1∨P5）∪C28∪P2的优美标号：P1的标号为 23；P5上各点的标号依次为 14，18，15，17，16；C28上各点的标号与第一种标号相同；P2上各点的标号依次为21，31.注：（P1∨P5）的优美标号：P1的标号为 9；P5上各点的标号依次为0，4，1，3，2.

（P1∨P5）∪C32∪P2的优美标号：P1的标号为 25；P5上各点的标号依次为 16，20，17，19，18；C32上各点的标号与第一种标号相同；P2上各点的标号依次为24，34.注：（P1∨P5）的优美标号：P1的标号为 9；P5上各点的标号依次为0，4，1，3，2.

[1]马克杰.优美图[M].北京：北京大学出版社，1991.

[2]杨显文.关于 C4m蛇的优美性[J].工程数学学报，1995，12（4）：108-112.

[3]吴跃生.关于圈 C4h的（r1，r2，…，r4h）-冠的优美性[J].华东交通大学学报，2011，28（1）：77-80.

[6]张志尚，张庆成，王春月.关于（s＜C4：n＞）∪Pm的优美性[J].东北师范大学学报：自然科学版，2011，43（3）：14-18.

[10]张志尚，王春月，张庆成.关于wn∪wn∪Pm的优美性[J].东北师范大学学报：自然科学版，2010，42（4）：30-34.

[11]吴跃生，徐保根.两类非连通图（P2∨Kn）（0，0，r1，0，…，0，rn）∪St（m）及（P2∨Kn）（r1+a，r2，0，…，0，）∪Gr的优美性[J].中山大学学报：自然科学版，2012，51（5）：63-66.

[12]王涛，刘海生，李德明.和轮相关图的优美性[J].中山大学学报：自然科学版，2011，50（6）：16-19.

[14]蔡华，魏丽侠，吕显瑞.非连通图（P1∨Pn）∪Gr和（P1∨Pn）∪（P3∨Kr）及Wn∪St（m）的优美性[J].吉林大学学报：理学版，2007，45（4）：539-543.

[15]蔡华.几类非连通图的优美性[D].长春：吉林大学，2007.

[16]吴跃生，王广富，徐保根.非连通图C2n+1∪Gn-1的优美性[J].华东交通大学学报，2012，29（6）：26-29.

[17]GALLIAN JA.A dynamic survey of graph labeling[J].The Electronic Journal of Combinatorics，2013，16（6）：1-308.

[18]魏丽侠，张昆龙.图K1∨Cn的非连通并图的优美性[J].中山大学学报：自然科学版，2007，46（4）：13-16.

[19]吴跃生.关于圈 C4h+3的（Gr1，Gr2，…，Gr4h+3）-冠的优美性[J].吉首大学学报：自然科学版，2013，34（4）：4-9.

[20]吴跃生，王广富.非连通图的优美性[J].合肥工业大学学报：自然科学版，2013，36（8）：1010-1012.