陈 琴

（中国计量学院 理学院，浙江 杭州 310018）

本文只考虑有限简单图.令G＝（V，E）是一个含有m 条边的无向图，f：E→｛1，2，…，m｝为G的一个双射.对每个顶点u∈V，u上的边权和f＋（u）定义为.若对G的任意两个不同的顶点u和v，都有f＋（u）≠f＋（v），则称f为G 的一个反魔术标号，具有反魔术标号的图称为反魔术图.在1990年，Hartsfield和 Ringel［1］引入了反魔术图的概念，并猜测：除K2外的所有连通图都是反魔术图.尽管这个猜想受到了广泛关注，但至今尚未解决.Hartsfield和 Ringel［1］证明了路、圈、轮和完全图是反魔术图.Alon［2］证明了存在常数C使得最小度δ（G）满足δ（G）＞Clog｜V（G）｜的图都是反魔术图，其中｜V（G）｜表示G的顶点数，他们同时证明了最大度Δ（G）满足Δ（G）≥｜V（G）｜－2的图是反魔术图.文献［3］证明了两条路的Cartesian乘积图以及一条路和一个圈的Cartesian乘积图都是反魔术图.Shang［4］证明了所有蛛形图是反魔术图.文献［5］证明了所有三正则图是反魔术的，最近此结果被更新到所有奇正则图是反魔术的［6］.更多反魔术图类的证明可参见文献［7、8、9、10］.

在探索不含三角形且具有任意大色数的图类时，Mycielski介绍了一种新的图构造法：图G的Mycielskian图，记作μ（G），μ（G）的顶点集为V∪V′∪｛w｝，其中V′＝｛x′｜x∈V｝，边集为E∪｛xy′｜xy∈E｝∪｛y′w｜y′∈V′｝，顶点x′是顶点x 的对，顶点w称为μ（G）的根.

本文证明路、圈的 Mycielskian图是反魔术图.

1 μ（Pn）是反魔术图

定理1 设Pn（n≥3）是具有n个顶点的路，则μ（Pn）是反魔术图.

证明 记Pn的顶点集为｛v1，v2…，vn｝，边集为｛vivi＋2｜i＝1，2，…，n－2｝∪｛vn－1vn｝.为方便起见，顶点集V和V′之间的2（n－2）条边记作ei1＝vi＋2v′i和ei2＝viv′i＋2（i＝1，2，…，n－2）.记e（n－1）1＝vnv′n－1，e（n－1）2＝vn－1v′n.下面依据n的奇偶性，分两种情形来构造μ（Pn）的反魔术标号.

情形1 n是偶数

由于μ（P2）与C5同构，其反魔术性已被证实，所以不妨设n≥4.首先给边wv′i（i＝1，2，…，n）标上2i－1，对每条边vivj∈E（Pn），给边vn－1vn标上2n－2，边vivi＋2（i＝1，2，…，n－2）标上2i.最后按e11，e12，e21，e22，…，e（n－1）1，e（n－1）2的顺序依次给2n－2条边eij（i＝1，2，…，n－1）标上2n，2n＋1，…，2n＋2n－3.下面证明上述标号是反魔术的.

断言1.1（a）：

f＋（v1）＜f＋（v2）＜…＜f＋（vn）且f＋（v′1）＜f＋（v′2）＜…＜f＋（v′n）.

证明 首先考察集合V中的顶点.不难得到f＋（v1）＝2n＋3和f＋（v2）＝2n＋7.当i＝3，4，…，n－1时有

又f＋（vn）＝2（n－2）＋2（n－1）＋4n＋2（n－2）＋2（n－2）－2＝12n－16.观察发现f＋（v3）＝4n＋13＞f＋（v2）和 f＋（vn－1）＝12n－19＜f＋（bn）.因此不等式f＋（v1）＜f＋（v2）＜…＜f＋（vn）成立.

对每一顶点v′i∈V′，首先有f＋（v′1）＝2n＋1和f＋（v′2）＝2n＋5.计算可得：当i＝3，4，…，n－1时有f＋（v′i）＝2i－1＋4n＋4（i－2）＋1＝6i＋4n－8，f＋（v′n）＝2n－1＋4n＋2（n－2）＋4（n－2）＝10n－9.从而由不等式f＋（v′3）＝4n＋10＞f＋（v′2）和f＋（vn－1）＝10n－14＜f＋（v′n），可推出不等式f＋（v′1）＜f＋（v′2）＜…＜f＋（v′n）成立.断言1.1（a）证毕.

断言1.1（b） f＋（vi）≠f＋（v′j），i，j＝1，2，…，n.

证明 由断言1.1（a）的证明可知，除f＋（vn）外的所有f＋（vi）都是奇数，除f＋（v′1）、f＋（v′2）和f＋（v′n）外的所有f＋（v′i）都是偶数.由于f＋（v′1）＜f＋（v1）＜f＋（v′2）＜f＋（v2），所以只需验证：

1）f＋（vn）≠f＋（v′i），i＝3，4，…，n－1，

2）f＋（v′n）≠f＋（vi），i＝1，2，…，n－1.

事实上，当n≥4时，有f＋（vn）＝12n－16＞10n－9＝f＋（v′n），所以f＋（vn）＞f＋（v′n）＞f（v′n－1）＞…＞f（v′1），则1）成立.又f＋（v′n）＝10n－9及f＋（v2）＝2n＋7，因此当n≥4时有f＋（v′n）＞f＋（v2）＞f＋（v1）.若对某一i∈｛3，4，…，n－1｝有8i＋4n－11＝10n－9，则4i－3n＝1.然而由于n是偶数，此等式不可能成立.所以2）成立.断言1.1（b）证毕.

断言1.1（c） f＋（w）不等于f＋（vi）或f＋（v′i），i＝1，2，…，n.

情形2 n≥3是奇数

首先给边wv′i（i＝1，2，…，n－1）标上2i－1，边wv′n标上4n－3.对每条边vivj∈E（Pn），同情形1类似，给边vn－1vn标上2n－2，边vivi＋2（i＝1，2，…，n－2）标上2i.最后按e11，e12，e21，e22，…，e（n－1）1，e（n－1）2的顺序依次给2n－2条边eij（i＝1，2，…，n－1）标上2n－1，2n，…，2n＋2n－4.下面证明上述标号是反魔术的.

断言1.2（a）

f＋（v1）＜f＋（v2）＜…＜f＋（vn）且f＋（v′1）＜f＋（v′2）＜…＜f＋（v′n）.

证明 首先考察集合V中的顶点.我们有f＋（v1）＝2＋2n，f＋（v2）＝2n＋6以及f＋（vn）＝2（n－2）＋2（n－1）－2＋4n＋2n－7＋2n－5＝12n－18.又对i＝3，4，…，n－1，有f＋（vi）＝2（i－2）＋2i＋4n＋4（i－3）＋3＝8i＋4n－13.由于f＋（v3）＝4n＋11＞f＋（v2）和f＋（vn－1）＝12n－21＜f＋（vn），不等式f＋（v1）＜f＋（v2）＜…＜f＋（vn）成立.

对每一顶点v′i∈V′，首先注意到f＋（v′1）＝2n和f＋（v′2）＝3＋2n＋1＝2n＋4.当i＝3，4，…，n－1时计算得f＋（v′i）＝2i－1＋4n＋4（i－3）＋3＝6i＋4n－10，f＋（v′n）＝4n－3＋4n＋2（n－2）＋2（n－3）＝12n－13.所以由不等式f＋（v′3）＝4n＋8＞f＋（v′2）和f＋（vn－1）＝10n－16＜f＋（v′n），可得不等式f＋（v′1）＜f＋（v′2）＜…＜f＋（v′n）.断言1.2（a）证毕.

断言1.2（b） f＋（vi）≠f＋（v′j），i，j＝1，2，…，n.

证明 由断言1.2（a）的证明可知，除f＋（v1）、f＋（v2）和f＋（vn）外的所有f＋（vi）都是奇数，除f＋（v′n）外的所有f＋（v′i）都是偶数.由于f＋（v′1）＜f＋（v1）＜f＋（v′2）＜f＋（v2），我们只需验证：

1）f＋（vn）≠f＋（v′i），i＝1，2，…，n－1，

2）f＋（v′n）≠f＋（vi），i＝3，4，…，n－1，

3）f＋（v2）≠f＋（v′i），i＝3，4，…，n－1.

由于f＋（vn）＝12n－18＞4n＋6（n－1）－10＝f＋（v′n－1），则1）成立.又f＋（v′n）＝12n－13.若对某一i∈｛3，4，…，n－1｝有8i＋4n－13＝12n－13，则i＝n，矛盾.因此2）成立.由于f＋（v′3）＝4n＋8＞2n＋6＝f＋（v2），则3）成立.断言1.2（b）证毕.

断言1.2（c） f＋（w）不等于f＋（vi）或f＋（v′i），i＝1，2，…，n.

1）f＋（w）≠f（vn），

2）f＋（w）≠f（v′n），i＝3，4，…，n－1.

事实上，若n2＋2n－2＝12n－13，则n2－10n＋11＝0，n无整数解，所以1）成立.若n2＋2n－2＝8i＋4n－13且i≤n－1，则n≤7.当3≤n≤7且n为奇数时，容易验证无整数满足等式n2＋2n－2＝8i＋4n－13.因此2）成立.定理1证毕.

2 μ（Cn）（n≥3）是反魔术图

定理2 设Cn（n≥3）是具有个顶点的圈，则μ（Cn）是反魔术图.

证明 记Cn的顶点集为｛v1，v2…，vn｝，边集为｛v1v2｝∪｛vivi＋2｜i＝1，2，…，n－2｝∪｛vn－1vn｝.类似地，我们依据n的奇偶性，分两种情形来构造μ（Cn）的反魔术标号.

情形1 n≥4是偶数

断言2.1（a）

f＋（v1）＜f＋（v2）＜…＜f＋（vn）且f＋（v′2）＜f＋（v′1）＜f＋（v′4）＜f＋（v′3）＜…＜f＋（v′n）＜f＋（v′n－1）.

证明 对顶点vi∈V，注意到f＋（v1）＝4n＋13及f＋（v2）＝4n＋15.当i＝1，2，…时，有f＋（b2i＋1）＝10＋4n＋16i和f＋（v2i＋2）＝12＋4n＋16i.最后有f＋（vn－1）＝12n－9，f＋（vn）＝12n－7.由于f＋（v3）＝4n＋26＞f＋（v2）和f＋（vn－2）＝4n＋12＋16×＝12n－20＜12n－9＝f＋（vn－1），所以不等式f＋（v1）＜v＋（v2）＜…＜f＋（vn）成立.

对顶点v′i∈V′，当i＝1，2，…，时，有

（a）f＋（v′2i）＝12（i－1）＋5＋4n＝4n＋12i－7，

（b）f＋（v′2i－1）＝12（i－1）＋9＋4n＝4n＋12i－3.

容易验证不等式 f＋（v′2）＜f＋（v′1）＜f＋（v′4）＜f＋（v′3）…＜f＋（v′n）＜f＋（v′n－1）成立.断言2.1（a）证毕.

断言2.1（b） f＋（vi）≠f＋（v′j），i，j＝1，2，…，n.

证明 由断言2.1（a）的证明可知，除f＋（v1）、f＋（v2）、f＋（vn－1）和f＋（vn）外的所有f＋（vi）都是偶数，所有f＋（v′i）都是奇数.所以我们只需验证f＋（vj）≠f＋（v′k），j＝1，2，n－1，n；k＝1，2，…，n.

1.f＋（v1）≠f＋（v′k）.容易验证等式4n＋13＝4n＋12i－7及4n＋13＝5n＋12i－3中i都没有整数解.

2.f＋（v2）≠f＋（v′k）.同样的，等式4n＋15＝4n＋12i－7及4n＋15＝4n＋12i－3中i都没有整数解.

3.f＋（vn－1）≠f＋（v′k）.若12n－9＝4n＋12i－7，则有6i＋1＝4n，然而由于6i＋1是奇数，4n是偶数，此等式不可能成立.同理，12n－9≠4n＋12i－3.

4.f＋（vn）≠f＋（v′k）.若12n－7＝4n＋12i－7，则有，这与矛盾.同理，12n－7≠4n＋12i－7.断言2.1（b）证毕.

断言2.1（c） f＋（w）不等于f＋（vk）或f＋（v′k），k＝1，2，…，n.

为偶数，所以只需验证f＋（w）≠f（vk），k＝3，4，…，n－2.

f＋（v1）＜…＜f＋（v4）＜f＋（v8）＜f＋（v5）＜f＋（v6）＜f＋（v7）＜f＋（v9）＜f＋（v10）顶点集V′中的边权和没有发生改变.由于f＋（v8）的奇偶性没有改变，断言2.1（b）仍成立，并且由于f＋（v10）＝12×10－7＝113和f＋（v′9）＝12（5－1）＋9＋4×10＝97，可见断言2.1（c）对μ（C10）也成立.

情形2 n≥3是奇数

断言2.2（a）

f＋（v1）＜f＋（v2）＜…＜f＋（vn）且f＋（v′2）＜f＋（v′1）＜f＋（v′4）＜f＋（v′3）＜…＜f＋（v′n）＜f＋（v′n－1）.

证明 类似于情形1，对顶点vi∈V，我们有

（a）f＋（v1）＝2＋4＋（2n－1）＋（2n＋5）＝4n＋10，

（b）f＋（v2）＝2＋6＋（2n＋1）＋（2n＋4）＝4n＋13.

对每一顶点v′i∈V′，首先有f＋（v′2）＝4n＋2f＋（v′1）＝4n＋7和f＋（v′n）＝12n－3.当i＝1，2，…，时，有f＋（v′2i）＝4n＋12i－9和f＋（v′2i－1）＝12（i－1）＋9＋4n＝4n＋12i－5.由f＋（v′4）＝4n＋15＞f＋（v′1）及f＋（v′n－2）＝10n－11＜f＋（v′n），得断言2.2（a）成立.

断言2.2（b） f＋（vi）≠f＋（v′j），i，j＝1，2，…，n.

证明 由于除f＋（v2）和f＋（vn）外的所有f＋（vi）都是偶数，除f＋（v′2）外所有的f＋（v′i）都是奇数.所以我们只需验证：

1）f＋（vi）≠f＋（v′j），i＝2，n；j＝1，3，…，n，

2）f＋（v′2）≠f＋（vi），i＝1，3，…，n－1.

事实上，若n＝3，则f＋（v2）＝25，f＋（v′1）＝19和f＋（v′3）＝33；若n≥5，由于f＋（v2）＝4n＋13，f＋（v′1）＝4n＋7和f＋（v′4）＝4n＋15，结合断言 2.2（a），我 们 有 f＋（v′1）＜f＋（v2）＜f＋（v′4）＜f＋（v′3）…＜f＋（v′n）.所以f＋（v2）≠f＋（vj），j＝1，3，…，n.由于f＋（v′n）＝12n－3＞12n－9＞10n－11＝f＋（v′n－2），再由断言2.2（a）可得 f＋（v′n）＞f＋（vn）＞f＋（v′n－2）＞ … ＞f＋（v1），所以f＋（vn）≠f＋（vj），j＝1，3，…，n.因此1）成立.2）成立是因为f＋（v′2）＝4n＋2＜4n＋10＝f＋（v1）.

断言2.2（c） f＋（w）不等于f＋（vk）或f＋（v′k），k＝1，2，…，n.

3 结 语

本文通过给出具体标号方案，证明了路和圈的Mycielskian图是反魔术标号的.由于路和圈都已被证实是反魔术图，我们大胆提出以下猜想：

猜想 若图G是反魔术图，则μ（G）也是反魔术图.

［1］HARTSIELD N，RINGEL G.Pearls in Graph Theory［M ］.Boston：Academic Press，1990：108－109.

［2］ALON N，KAPLAN G，LEV A，et al.Dense graphs are antimagic［J］.Journal of Graph Theory，2004，47（4）：297－309.

［3］CHENG Yongxi.Lattice grids and prisms are antimagic［J］.Theoretical Computer Science，2007，374（1－3）：66－73.

［4］SHANG J L.Spiders are antimagic［J］.Ars Combinatoria，2015，118：367－372.

［5］LIANG Y，ZHU X.Anti－magic labeling of cubic graphs［J］.Journal of Graph Theory，2014，75：31－36.

［6］CRANSTON D W，LIANG Y，ZHU X.Regular graphs of odd degree are antimagic［J］.Journal of Graph Theory，2015，80（1）：28－33.

［7］ARUMUGAM S，MILLER M，PHANALASY O.Antimagic labeling of generalized Pyramid graphs［J］.Acta Mathematica Sinica（English Series），2014，30（2）：283－290.

［8］CRANSTON D W.Regular bipartite graphs are antimagic［J］.Journal of Graph Theory，2009，60（3）：173－182.

［9］LIANG Y，WONG T，ZHU X.Anti－magic labeling of trees［J］.Discrete Mathematics，2014，331：9－14.

［10］SHANGH J L，LIN C，LIAW S C.On the antimagic labeling of star forests［J］.Utilitas Mathematica，2015，97：373－385.