再探非连通图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－14］。文献［2］已经证明非连通图2C4（3m－1）∪C8m－1是优美图。

文献［14］讨论了非连通图2C4（3m－1）∪C8m－1∪G 的优美性，给出了非连通图2C4（3m－1）∪C8m－1∪G 是优美图的一个充分条件：对任意正整数m，如果图G是特征为k且缺k＋12m－3标号值的交错图（12 m－3≤k＋12 m－3≤｜E（G）｜），则非连通图2C4（3m－1）∪C8m－1∪G 存在缺标号值k＋1的优美标号。

本文将继续讨论非连通图2C4（3m－1）∪C8m－1∪G 的优美性，给出非连通图2C4（3m－1）∪C8m－1∪G 是优美图的另外5个充分条件。

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

2 主要结论及其证明

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

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

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

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

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

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

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

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

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

类似定理1的证明，可以证明θ就是非连通图2C4（3m－1）∪C8m－1∪G的缺k＋32 m－9标号值的优美标号。

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

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

类似定理1的证明，可以证明θ就是非连通图2C4（3m－1）∪C8m－1∪G的缺k＋1标号值的优美标号。

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

证明 把2C4（3m－1）中的 一 个 圈 记 作，另 一 个 记作，设V（）＝ ｛x1，x2，…，x4（3m－1）｝，）＝ ｛x1x2，x2x3，…，x12m－5x12m－4，x12m－4x1｝，V（）＝｛y1，y2，…，y12m－4｝，E（）＝｛y1y2，y2y3，…，y12m－5y12m－4，y12m－4y1｝，V（C8m－1）＝ ｛z1，z2，…，z8m－1｝，E（C8m－1）＝｛z1z2，z2z3，…，z8m－2z8m－1，z8m－1z1｝，设 X，Y 是图G的一个二分化，θ1是图G的交错标号，且（v）＝k＜（v）＝k＋1，｜E（G）｜＝q。

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

类似定理1的证明，可以证明θ就是非连通图2C4（3m－1）∪C8m－1∪G的缺k＋20 m－5标号值的优美标号。

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

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

类似定理1的证明，可以证明θ就是非连通图2C4（3m－1）∪C8m－1∪G的缺k＋12 m－4标号值的优美标号。

定义2［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。

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

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

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

例1 由推论，当m＝1，n＝18，r＝0时，非连通图2C8∪C7∪C72存在缺标号值50的优美标号为：

由推论，当m＝1，n＝9，r＝1时，非连通图2C8∪C7∪C36（1，1，…，1）存在缺标号值50的优美标号为：

由推论，当m＝1，n＝6，r＝2时，非连通图2C8∪C7∪C24（2，2，…，2）存在缺标号值50的优美标号为：

由推论，当m＝1，n＝3，r＝5时，非连通图2C8∪C7∪C12（5，5，…，5）存在缺标号值50的优美标号为：

由推论，当m＝1，n＝2，r＝8时，非连通图2C8∪C7∪C8（8，8，…，8）存在缺标号值50的优美标号为：

由推论，当m＝1，n＝1，r＝17时，非连通图2C8∪C7∪C4（17，17，17，17）存在缺标号值50的优美标号为：

［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.

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

［8］ 吴跃生.图 C7（r1，r2，r3，r4，r5，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，2007，16（DS6）：1－58.

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

［14］ 吴跃生.非连通图2C4（3m－1）∪C8m－1∪G 的优美标号［J］.唐山学院学报，2014，27（3）：12－14.

［15］ 吴跃生.非连通图 G＋e∪Hk－1的优美性［J］.吉首大学学报：自然科学版，2014，35（2）：3－5.

［16］ 吴跃生.非连通图C4m－1∪G的优美标号［J］.吉首大学学报：自然科学版，2014，35（3）：1－3.

［17］ 贾慧羡，左大伟.与扇图相关的2类图的超边优美标号［J］.吉首大学学报：自然科学版，2014，35（2）：6－9.