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

吴跃生

(华东交通大学理学院，江西 南昌 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的优美标号；对任意正整数m，若图G是特征为k且缺k+m标号值的交错图(m≤k+m≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+4m-1的优美标号.证明了:对任意正整数m，非连通图C4m-1∪C12m-12存在缺标号值10m-8的优美标号；对任意正整数m，非连通图C4m-1∪C4m-4存在缺标号值6m-4的优美标号.

笔者继续讨论非连通图C4m-1∪G的优美性，再给出非连通图C4m-1∪G是优美图的2个充分条件.将证明:对任意正整数m，非连通图C4m-1∪C8m-4存在缺标号值4m-3的优美标号;对任意正整数m(m≥2)，非连通图C4m-1∪C8m-8存在缺标号值7m-6的优美标号.

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

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

2 主要结果及其证明

定理1对任意正整数m，若图G是特征为k且缺k+2m标号值的交错图(2m≤k+2m≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+m的优美标号.

定义C4m-1∪G的顶点标号θ为：

下面证明θ是非连通图C4m-1∪G的优美标号.

(ⅰ)θ:X→[0，k]是单射(或双射)；θ:Y→[k+4m，q+4m-1]-{6m-1+k}是单射;θ:V(C4m-1)→[k+1，k+4m-1]∪{6m-1+k}-{k+m}是单射;θ:V(C4m-1∪G)→[0，q+4m-1]-{k+m}是单射.

(ⅱ)θ′:E(C4m-1)→[1，4m-1]是双射；θ′：E(G)→[4m，q+4m-1]是双射.θ′：E(C4m-1∪G)→[1，q+4m-1]是一一对应.

由(ⅰ)和(ⅱ)可知，θ就是非连通图C4m-1∪G的缺k+m标号值的优美标号.证毕.

定理2对任意正整数m(m≥2)，若图G是特征为k且缺k+2m-1标号值的交错图(2m-1≤k+2m-1≤|E(G)|)，则非连通图C4m-1∪G存在缺标号值k+3m-1的优美标号.

定义C4m-1∪G的顶点标号θ为：

下面证明θ是非连通图C4m-1∪G的优美标号.

(ⅰ)θ:X→[0，k]是单射(或双射);θ:Y→[k+4m，q+4m-1]-{6m-1+k}是单射;θ:V(C4m-1)→[k+1，k+4m-1]∪{6m-2+k}-{k+3m-1}是单射;θ:V(C4m-1∪G)→[0，q+4m-1]-{k+3m-1}是单射.

(ⅱ)θ′:E(C4m-1)→[1，4m-1]是双射；θ′：E(G)→[4m，q+4m-1]是双射.θ′：E(C4m-1∪G)→[1，q+4m-1]是一一对应.

由(ⅰ)和(ⅱ)可知，θ就是非连通图C4m-1∪G的缺k+3m-1标号值的优美标号.证毕.

定义4[5-8]V(G)= {u1，u2，…，un}的每个顶点ui都粘接了ri条悬挂边(ri为自然数，i=1，2，…，n)所得到的图，称为图G的(r1，r2，…，rn)-冠，简记为 G(r1，r2，…，rn).特别地，当r1=r2=… =rn=r时，称为图G的r-冠.图G的0-冠就是图G.

引理1[5]对任意正整数m，任意自然数r，则C4m(r，r，…，r)存在特征为2m(r+1)-1，且缺3m(r+1)的交错标号.

注意到3m(r+1)=(2m(r+1)-1)+m(r+1)+1，由定理1和引理1有以下结论：

推论1对任意正整数m，n，任意自然数r，当2m-1=n(r+1)时，非连通图C4m-1∪C4n(r，r，…，r)存在缺标号值5m-3的优美标号.特别地，当r=0时，对任意正整数m，非连通图C4m-1∪C8m-4存在缺标号值5m-3的优美标号.

例1由推论1给出的当m=4，n=7，r=0时，非连通图C15∪C28存在缺标号值17的优美标号为:

28，14，27，15，26，16，25，18，24，19，23，20，22，21，36;

0，43，1，42，2，41，3，40，4，39，5，38，6，37，7，35，8，34，9，33，10，32，11，31，12，30，13，29.

由推论1给出的当m=4，n=1，r=6时，非连通图C15∪C4(6，6，6，6)存在缺标号值17的优美标号为:

28，14，27，15，26，16，25，18，24，19，23，20，22，21，36;

0(43，42，41，40，39，38)，37(1，2，3，4，5，6)，7(35，34，33，32，31，30)，29(8，9，10，11，12，13).

注意到3m(r+1)=(2m(r+1)-1)+m(r+1)+1，由定理2和引理1有以下结论：

推论2对任意正整数m，n，任意自然数r，当2m-2=n(r+1)时，非连通图C4m-1∪C4n(r，r，…，r)存在缺标号值7m-6的优美标号.特别地，当r=0时，对任意正整数m，非连通图C4m-1∪C8m-8存在缺标号值7m-6的优美标号.

例2由推论2给出的当m=5，n=8，r=0时，非连通图C19∪C32存在缺标号值29的优美标号为:

34，16，33，17，32，18，31，19，30，20，28，21，27，22，26，23，25，24，43;

0，51，1，50，2，49，3，48，4，47，5，46，6，45，7，44，8，42，9，41，10，40，11，39，12，38，13，37，14，36，15，35.

由推论2给出的当m=4，n=4，r=1时，非连通图C19∪C16(1，1，…，1)存在缺标号值29的优美标号为:

34，16，33，17，32，18，31，19，30，20，28，21，27，22，26，23，25，24，43;

0(51)，50(1)，2(49)，48(3)，4(47)，46(5)，6(45)，44(7)，8(42)，41(9)，10(40)，39(11)，12(38)，37(13)，14(36)，35(15).

由推论2给出的当m=4，n=2，r=3时，非连通图C19∪C8(3，3，…，3)存在缺标号值29的优美标号为:

34，16，33，17，32，18，31，19，30，20，28，21，27，22，26，23，25，24，43;

0(51，50，49)，48(1，2，3)，4(47，46，45)，44(5，6，7)，8(42，41，40)，39(9，10，11)，12(38，37，36)，35(13，14，

15).

由推论2给出的当m=4，n=1，r=7时，非连通图C19∪C8(3，3，…，3)存在缺标号值29的优美标号为:

34，16，33，17，32，18，31，19，30，20，28，21，27，22，26，23，25，24，43;

0(51，50，49，48，47，46，45)，44(1，2，3，4，5，6，7)，8(42，41，40，39，38，37，36)，35(9，10，11，12，13，14，15).

由C4m-1是优美图和引理2有以下结论：

由推论1和引理2有以下结论：

由推论2和引理2有以下结论：

由文献[13]可知，C4m-1∪C4m是优美图.再由引理2有以下结论：

由文献[13]可知，C4m-1∪C12m-8是优美图.再由引理2有以下结论：

由文献[17]可知，C4m-1∪C12m-12是优美图.再由引理2有以下结论：

由文献[17]可知，C4m-1∪C4m-4是优美图.再由引理2有以下结论：

[1] ROSE A.On Certain Valuations of the Vertices of a Graph[M]∥ROSENTHIEHL P，Ed..Theory of Graphs (Internat. Sympos.，Rome，1966).New York and Dunod Paris:Gordon and Breach，1967:349-355.

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

[3] 杨显文.关于C4m蛇的优美性[J].工程数学学报，1995，12(4):108-112.

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

[5] 吴跃生，李咏秋.关于圈C4h+3的(r1，r2，…，r4h+3)-冠的优美性[J].吉首大学学报:自然科学版，2011，32(6):1-4.

[6] 吴跃生.图C7(r1，r2，r3，r4，r5，0，0)∪St(m)的优美性[J].吉首大学学报:自然科学版，2012，33(5):1-9.

[7] 吴跃生，徐保根.两类非连通图(P2∨K的优美性[J].中山大学学报:自然科学版，2012，51(5):63-66.

[8] 吴跃生.关于图P36k+5∪P3n的优美性[J].吉首大学学报:自然科学版，2012，33(3):4-7.

[9] 吴跃生，王广富，徐保根.关于C4h+1⊙K1的(Gr1，Gr2，…，Gr4h+1，Gr4h+2)-冠的优美性[J].山东大学学报：理学版，2013，48(4):25-27.

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

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

[12] JOSEPH A GALLIAN.A Dynamic Survey of Graph Labeling[J].The Electronic Journal of Combinatorics，2013，16(DS6):1-308.

[13] 吴跃生.非连通图C4m-1∪G的优美标号[J].吉首大学学报:自然科学版，2014，35(3):1-3.

[14] 吴跃生.非连通图D2，8∪G的优美性[J].西华师范大学学报:自然科学版，2014:35(1):4-6.

[15] 吴跃生.非连通图G+e∪Hk-1的优美性[J].吉首大学学报:自然科学版，2014，35(2):3-5.

[16] 贾慧羡，左大伟.与扇图相关的2类图的超边优美标号[J].吉首大学学报:自然科学版，2014，35(2):6-9.

[17] 吴跃生.再探非连通图C4m-1∪G的优美标号[J].吉首大学学报:自然科学版，2015，36(1):1-4.

[18] 吴跃生.非连通图Gn-1∪ki=0C3i(2n+1)的优美性[J].河南教育学院学报，2013，22(4):7-9.

(责任编辑 向阳洁)

Further Exploration of the Graceful Labeling of the Unconnected GraphC4m-1∪G

WU Yuesheng

(School of Basic Science，East China Jiaotong University，Nanchang 330013，China )

The gracefulness of the unconnected graphC4m-1∪Gis discussed.Two sufficient conditions are given for the gracefulness of unconnected graphC4m-1∪G.

graceful graph;alternating graph;unconnected graph;graceful labeling

1007-2985(2015)04-0005-04

吴跃生(1959—)，男，江西瑞金人，华东交通大学理学院副教授，硕士，主要从事图论研究.

O157.5

A

10.3969/j.issn.1007-2985.2015.04.002