非连通图2C4（3m－1）∪C8m－1∪G 的优美标号

吴跃生

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

1 相关概念

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

图的优美标号问题是组合数学中一个热门课题［1－13］。文献［2］已经证明：非连通图2C4（3m－1）∪C8m－1是优美图。

本文拟讨论非连通图2C4（3m－1）∪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的一组优美标号，称θ′为G的边上的由θ导出的诱导值。

定义2［1］设f为G的一个优美标号，如果存在一个正整数k，使得对任意的uv∈E（G）有

成立，则称f为G的平衡标号（或称G有平衡标号f），且称k为f的特征，图G称为平衡二分图（balanced bipartite graph）。

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

定义3［1］在平衡二分图G中，设其优美标号θ的特征为k，并且θ（u0）＝k，θ（v0）＝k＋1，则称u0为G的二分点，v0为G的对偶二分点。

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

2 主要结论及其证明

定理 对任意正整数m，如果图G是特征为k且缺k＋12m－3标号值的交错图（12m－3≤k＋12m－3≤｜E（G）｜），非连通图2C4（3m－1）∪C8m－1∪G存在缺标号值k＋1的优美标号。

证明 把2C4（3m－1）中 的 一 个 圈 记 作另 一 个 记设X，Y是图G的一个二分化，θ1是图G的交错标号，且

定义2C4（3m－1）∪C8m－1∪G的顶点标号θ为：

下面证 明θ是 非 连 通 图 2C4（3m－1）∪C8m－1∪G的 优 美标号。

（1）θ：X→［0，k］是单射（或双射）；θ：Y→［k＋32m－8，q＋32m－9］－｛44m＋k－12｝是单射（或双射）；

θ：→［k＋2，6m＋k－1］∪［26m＋k－7，32m＋k－9］－｛29m＋k－8｝是单射（或双射）；

θ：V（）→［6m＋k＋1，12m＋k－2］∪［20m＋k－3，26m＋k－8］－｛29m＋k－8，44m＋k－12｝是单射（或双射）；

θ：V（C）→［12m＋k－1，20m＋k－4］∪｛6m＋k｝是单射（或双射）；

θ：V（2C4（3m－1）∪C8m－1∪G）→［0，q＋32m－9］－｛k＋1｝是单射。

（2）θ′：E（）→［20m－6，32m－11］是双射；

θ′：E（）→［8m，20m－7］∪｛32m－10，32m－9｝是双射；

θ′：E（C8m－1）→［1，8m－1］是双射；

θ′：E（G）→［32m－8，q＋32m－9］是双射；

θ′：E（2C4（3m－1）∪C8m－1∪G）→ ［1，q＋32m－9］是 一 一对应。

由（1）和（2）可知θ就是非连通图2C4（3m－1）∪C8m－1∪G的缺k＋1标号值的优美标号。

引理 对任意正整数n，设C4n是有4n个顶点的圈，则C4n存在特征为2n－1，且缺3n的交错标号。

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

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

注意到：3n＝（2n－1）＋n＋1，由定理和引理1有以下推论。

推论1 对任意正整数m，非连通图2C4（3m－1）∪C8m－1∪C48m－16存在缺标号值24m－8的优美标号。

例1 由推论1，非连通图2C8∪C7∪C32存在缺标号值16的优美标号为：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0，55 ，1，54，2，53，3，52，4，51，5，50，6，49，7，48，8，46，9，45，10，44，11，43，12，42，13，41，14，40，15，39.

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

引理2［3］对任意正整数m，任意自然数r1，r2，…，rm，则C4m（r1，0，r2，0，…，rm，0，…，0）存在特征为2m－1，且缺3m的交错标号。

注意到：3m＝（2m－1）＋m＋1，由定理和引理2有下面的推论。

推论2 对任意正整数m，任意自然数r1，r2，…，r12m－4，非连通图2C4（3m－1）∪C8m－1∪C48m－16（r1，0，r2，0，…，r12m－4，0，0，…，0）存在缺标号值24m－8的优美标号。

例2 由推论2，非连通图2C8∪C7∪C32（1，0，2，0，3，0，4，0，5，0，6，0，7，0，8，0，0，…，0）存在缺标号值16的优美标号为：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0（91），90，1（89，88），87，2（86，85，84），83，3（82，81，80，79），78，4（77，76，75，74，73），72，5（71，70，69，68，67，66），65，6（64，63，62，61，60，59，58），57，7（56，55，54，53，52，51，50，49），48，8，46，9，45，10，44，11，43，12，42，13，41，14，40，15，39.

引理3［3］对任意正整数m，任意自然数r，则C4m（r，r，…，r）存在特征为2m（r＋1）－1，且缺3m（r＋1）的交错标号。

注意到：3m（r＋1）＝（2m（r＋1）－1）＋m（r＋1）＋1，由定理和引理3有下面的推论。

推论3 对任意正整数m，n，任意自然数r，当12m－4＝n（r＋1）时，非连通图2C4（3m－1）∪C8m－1∪C4n（r，r，…，r）存在缺2n（r＋1）标号值的优美标号。

例3 由推论3给出的非连通图2C8∪C7∪C16（1，1，…，1）缺16标号值的优美标号为：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0（55），54（1），2（53），52（3），4（51），50（5），6（49），48（7），8（46），45（9），10（44），43（11），12（42），41（13），14（40），39（15）.

由推论3给出的非连通图2C8∪C7∪C8（3，3，…，3）缺16标号值的优美标号为：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0（55 ，54，53），52（1，2，3），4（51，50，49），48（5，6，7），8（46，45，44），43（9，10，11），12（42，41，40），39（13，14，15）.

由推论3给出的非连通图2C8∪C7∪C4（7，7，7，7）缺16标号值的优美标号为：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0（55 ，54，53，52，51，50，49），48（1，2，3，4，5，6，7），8（46，45，44，43，42，41，40），39（9，10，11，12，13，14，15）.

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

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

推论4 对任意正整数m，n，当6m－2＝n时，非连通图2C4（3m－1）∪C8m－1∪2C4n存在缺24m－8标号值的优美标号。

例4 由推论4给出的非连通图2C8∪C7∪2C16缺16标号值的优美标号为：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

0，55 ，1，54，2，53，3，52，5，51，6，50，7，49，8，48；

46，9 ，45，10，44，11，43.4.42，12，41.13，40，14，39，15.

引理5［13］对任意正整数m（m≠3），mC4存在特征为2m－1，且缺3m的交错标号。

注意到：3m＝（2m－1）＋m＋1，由定理和引理5有下面的推论。

推论5 对任意正整数m，n，当12m－1＝n时，非连通图2C4（3m－1）∪C8m－1∪nC4存 在 缺 24m－8 标 号 值 的 优 美标号。

例5 由推论5给出的非连通图2C8∪C7∪8C4缺16标号值的优美标号为：

38，17 ，37，18，35，19，34，20；

33，22 ，32，23，36，24，47，25；

26，31 ，27，21，28，30，29；

55，0 ，53，1；54，3，48，5；52，2，50，6；51，4，43，11；

49，7 ，45，8；46，10，40，12；44，9，42，13；41，14，39，15.

［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］吴跃生.关于图P6k＋53∪Pn3的优美性［J］.吉首大学学报：自然科学版，2012，33（3）：4－7.

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

［8］吴跃生.图C7（r1，r2，r3，r4，r5，0，0）∪St（m）的优美性［J］.吉首大学学报：自然科学版，2012，33（5）：9－11.

［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］Gallian J A.A dynamic survey of graph labeling［J］.The Electronic Joumal of Combinatorics，2012，19，DS6：1－260.

［13］Jaromir Abrham，Anton Kotzig.All 2－regular graphs consisting of 4－cycles are graceful［J］.Discrete Mathematics，1994，135（1－3）：1－14.