路、圈的Mycielskian圖的反魔術標號

陳 琴

（中國計量學院 理學院，浙江 杭州 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.