非连通图2C4m∪C8m－1∪G的优美标号

吴跃生

（华东交通大学理学院，江西南昌330013）

非连通图2C4m∪C8m－1∪G的优美标号

吴跃生

（华东交通大学理学院，江西南昌330013）

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

优美图；平衡二分图；非连通图；优美标号

1 预备知识

图的优美标号问题是图论中一个富有挑战性的课题［1－13］.文献［1］已经证明：对任意正整数m，C4m和C4m－1都是优美的，而C4m＋1和C4m＋2都不是优美的.许多文献还研究了非连通图的优美性［2，5，13］.文献［2］证明了非连通图2C4m∪C8m－1是优美图.本文讨论了非连通图2C4m∪C8m－1∪G的优美性.

定义1［1］对于一个图G＝（V，E），如果存在一个单射θ：V（G）→［0，｜E（G）｜］，使得对所有边e＝（u，v）∈E（G），由θ′（e）＝｜θ（u）－θ（v）｜导出的映射θ′：E（G）→［1，｜E（G）｜］是一一对应的，则称图G是优美图，称θ是图G的优美标号.如果在集合［0，｜E（G）｜］存在整数a不是优美图G的标号值，则称整数a是优美图G的优美标号的缺失值，简称优美图G的缺失值.

定义2［3］G是一个优美二部图，其优美标号为θ，V（G）划分成两个集合X，Y，如果，则称θ是G的交错标号，称G是在交错标号θ下的交错图，称k是交错标号θ的特征值.

定义3［4－5］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.

本文所讨论的图均为无向简单图，V（G）和E（G）分别表示图G的顶点集和边集.记号Gk＋m表示图G是特征为k且缺失值为k＋m的交错图.记号［m，n］表示整数集合｛m，m＋1，…，n｝，其中m和n均为非负整数，且满足0≤m＜n.未说明的符号及术语均同文献［1］.

2 结果及证明

定理1 对任意正整数m，4m＋1≤k＋4m＋1≤｜E（Gk＋4m＋1）｜，非连通图2C4m∪C8m－1∪Gk＋4m＋1存在缺失值为k＋1的优美标号.

证明 把2C4m中的一个圈记作，另一个记作，设V（）＝｛x1，x2，…，x4m｝，E（）＝｛x1x2，x2x3，…，x4m－1x4m，x4mx1｝，V）＝｛y1，y2，…，y4m｝，E（C4（2m））＝｛y1y2，y2y3，…，y4m－1y4m，y4my1｝，V（C8m－1）＝｛z1，z2，…，z8m－1｝，E（C8m－1）＝｛z1z2，z2z3，…，z8m－2z8m－1，z8m－1z1｝.设X，Y是图Gk＋4m＋1的一个二分化，θ1是图Gk＋4m＋1的交错标号，且

非连通图2C4m∪C8m－1∪Gk＋4m＋1的顶点标号θ定义为：

情况1.

θ：X→［0，k］是单射（或双射）；θ：Y→［k＋16m，q＋16m－1］－｛20m＋k｝是单射（或双射）.

所以，θ：V（2C4m∪C8m－1∪Gk＋4m＋1）→［0，q＋16m－1］－｛k＋1｝是单射.

情况2.

即

亦即

即

亦即

即

亦即

θ′：E（C8m－1）→［1，8m－1］是一一对应的.

θ′：E（Gk＋4m＋1）→［12m＋1，q＋12m］是一一对应的.

θ′：E（2C4m∪C8m－1∪Gk＋4m＋1）→［1，q＋16m－1］是一一对应的.

所以非连通图2C4m∪C8m－1∪Gk＋4m＋1是优美的，θ就是其缺失值为k＋1的优美标号.

引理1［4］对任意正整数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，当4m＝n（r＋1）时，非连通图2C4m∪C8m－1∪C4n（r，r，…，r）存在缺失值为2n（r＋1）的优美标号.

例1 当m＝2，n＝8，r＝0时，由推论1，非连通图C8∪C8∪C15∪C32的缺失值为16的优美标号为：C8：46，17，45，18，43，19，42，20，46；C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C32：0，63，1，62，2，61，3，60，4，59，5，58，6，57，7，56，8，54，9，53，10，52，11，51，12，50，13，49，14，48，15，47，0.

当m＝2，n＝4，r＝1时，由推论1给出的非连通图C8∪C8∪C15∪C16（1，1，…，1）的缺失值为16的优美标号为：

C8：46，17，45，18，43，19，42，20，46；C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C16（1，1，…，1）：0（63），62（1），2（61），60（3），4（59），58（5），6（57），56（7），8（54），53（9），10（52），51（11），12（50），49（13），14（48），47（15），0（63）.

当m＝2，n＝2，r＝3时，由推论1给出的非连通图C8∪C8∪C15∪C8（3，3，…，3）的缺失值为16的优美标号为：

C8：46，17，45，18，43，19，42，20，46；C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C8（3，3，…，3）：0（63，62，61），60（1，2，3），4（59，58，57），56（5，6，7），8（54，53，52），51（9，10，11），12（50，49，48），47（13，14，15），0（63，62，61）.

当m＝2，n＝1，r＝4时，由推论1给出的非连通图C8∪C8∪C15∪C4（7，7，7，7）的缺失值为16的优美标号为：

C8：46，17，45，18，43，19，42，20，46；C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C4（7，7，7，7）：0（63，62，61，60，59，58，57），56（1，2，3，4，5，6，7），8（54，53，52，51，50，49，48），47（9，10，11，12，13，14，15）.

引理2［6］对任意正整数m，2C4m存在特征为4m－1，且缺失值为6m的交错标号.

注意到6m＝（4m－1）＋2m＋1，由定理1和引理2有下面的结论.

推论2 对任意正整数m，非连通图2C4m∪C8m－1∪2C8m存在缺失值为8m的优美标号.

例2 当m＝2时，由推论2，非连通图2C8∪C15∪2C16的缺失值为16的优美标号为：

C8：46，17，45，18，43，19，42，20，46；

C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C16：0，63，1，62，2，61，3，60，5，59，6，58，7，57，8，56，0；

C16：54，9，53，10，52，11，51，4，50，12，49，13，48，14，47，15，54.

引理3［6］对任意正整数m，非连通图2C4m∪C8m存在特征为8m－1且存在缺失值为12m的交错标号.

注意到12m＝（8m－1）＋4m＋1，由定理1和引理3有下面的结论.

推论3 对任意正整数m，非连通图2C4m∪C8m－1∪（2C4m∪C8m）存在缺失值为8m的优美标号.

例3 当m＝2时，由推论3，非连通图2C8∪C15∪（2C8∪C16）的缺失值为16的优美标号为：

C8：46，17，45，18，43，19，42，20，46；

C8：41，22，40，23，44，24，55，25，41；

C15：26，39，27，38，28，37，29，36，21，35，30，34，31，33，32，26；

C8：0，63，1，62，2，60，3，59，0；

C8：5，58，6，61，7，57，8，56，5；

C16：54，9，53，10，52，11，51，4，50，12，49，13，48，14，47，15，54.

引理4［11］对任意自然数n，当n≥2时，C2n＋1是有2n＋1个顶点的圈，Gn－1是边数为n－1的优美图，则非连通图C2n＋1∪Gn－1是优美的.

因为E（2C4m∪C8m－1）＝16m－1，由引理4有下面的结论.

推论4 设m为任意的正整数，则非连通图（2C4m∪C8m－1）∪C2（16m）＋1是优美的.

引理5［12］当n，k为任意自然数，n≥2时，C3i（2n＋1）是有3i（2n＋1）个顶点的圈，Gn－1是边数为n－1的优美图，则非连通图是优美的.

因为E（2C4m∪C8m－1）＝16m－1，由引理5有下面的结论.

推论5 设m为任意的正整数，n为任意的正整数，则非连通图是优美的.

［1］ 马克杰.优美图［M］.北京：北京大学出版社，1991：1-247.

［2］ 董俊超.C4k∪C4k∪Cm的优美性［J］.烟台大学学报：自然科学与工程版，1999，12（4）：238-241.

［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］ 吴跃生，王广富，徐保根.非连通图2C4m∪G的优美性［J］.烟台大学学报：自然科学与工程版，2014，27（4）：240-243.

［7］ GALLIAN J A.A dynamic survey of graph labeling［J］.The Electronic Joumal of Combinatorics，2013，19，DS6：1-308.

［8］ 吴跃生，王广富，徐保根.非连通图C4m－1∪C4m∪G的优美标号［J］.西南大学学报：自然科学版，2014，36（8）：83-86.

［9］ 吴跃生，王广富，徐保根.关于图G∪T□K1的优美性［J］东北师大学报：自然科学版，2014，46（1）：14-16.

［10］ 吴跃生，王广富，徐保根.非连通图（P2∨Kn）（r1，r2，…，rn＋2）∪Gr的优美性［J］.东北师大学报：自然科学版，2014，46（3）：38-42.

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

［12］ 吴跃生.非连通图Gn－1∪kG3i（2n＋1）的优美性［J］.河南教育学院学报，2013，22（4）：7-9.

［13］ 吴跃生，王广富，徐保根.非连通图3C4m∪C8m－1∪G的优美标号［J］.天津师范大学学报：自然科学版，2014，34（2）：19-23.

θ′（zz）＝8m－2i－2，i＝1，2，…，2m－1；
2i2i＋1
｛8m－2i－1，i＝2m＋1，2m＋2，…，4m－1.θ′（z4mz4m＋1）＝8m－1，θ′（z8m－1z1）＝4m－2.

The graceful labeling of the unconnected graph 2C4m∪C8m－1∪G

WU Yue-sheng
（School of Science，East China Jiaotong University，Nanchang 330013，China）

The gracefulness of the unconnected graph 2C4m∪C8m－1∪Gis discussed.One sufficient condition is given for the gracefulness of unconnected graph 2C4m∪C8m－1∪G.

graceful graph；balanced bipartite graph；unconnected graph；graceful labeling

O 157.5 ［学科代码］ 110·7470

A

（责任编辑：陶 理）

1000-1832（2015）03-0060-04

10.16163／j.cnki.22-1123／n.2015.03.013

2013-12-17

国家自然科学基金资助项目（11261019，11361024）；江西省教育厅2014年度科学技术研究项目（GJJ14380）.

吴跃生（1959—），男，硕士，副教授，主要从事图论研究.