若干Mycielski圖鄰點可區別Ⅰ-均勻全染色

張 婷＊1， 朱 恩 強， 趙 雙 柱， 杜 佳

（1.蘭州文理學院 師范學院，甘肅 蘭州 730000；2.北京大學 信息科學技術學院，北京 100871；3.蘭州文理學院 數字媒體學院，甘肅 蘭州 730000）

0 引 言

關于均勻染色的概念最早是由Meyer［1］提出的，1994年，Fu［2］提出了均勻全染色概念以及均勻全染色猜想.許多學者圍繞圖的均勻全染色做了大量研究［3－5］.文獻［6-8］研究了一些特殊圖的點可區別Ⅰ-全染色和鄰點可區別Ⅰ-全染色.文獻［9］給出了路、圈、扇、輪、完全圖、完全二部圖的鄰點可區別Ⅰ-均勻全色數，提出鄰點可區別Ⅰ－均勻全色數最大不超過2的猜想；文獻［10］研究了幾類圖的均勻鄰點可區別Ⅰ-全染色.本文根據圖M（Pn）、M（Cn）和 M（Sn）的構造特征，利用函數構造法，研究并確立它們鄰點可區別Ⅰ-均勻全色數，并驗證其滿足猜想.

1 相關定義和引理

定義1［11］對于階數不小于2的連通圖G（V，E），設f是從V（G）∪E（G）到｛1，2，…，k｝的映射，k為自然數，如果f滿足

（1）對uv∈E（G），u≠v，有f（u）≠f（v）；

（2）對 uv，uw∈E（G），v≠w，f（uv）≠f（uw）；

（3）對uv∈E（G），u≠v，C（u）≠C（v）則稱f為圖G的一個鄰點可區別的Ⅰ-全染色（簡記為k-Ⅰ-AVDTC）.記χiat（G）＝min｛k｜G 的k-Ⅰ-AVDTC｝為圖G的鄰點可區別Ⅰ-全色數.其中C（u）＝｛f（u）｝∪｛f（uv）｜uv∈E（G）｝稱為點u在f下的色集，C（u）在色全集合C＝｛1，2，…，k｝中的補集記為C（v）＝C＼C（u）.

定義2［9］設f 是簡單連通圖G（V，E）（V（G）≥2）的一個k-Ⅰ-AVDTC，若滿足i，j∈｛1，2，…，k｝，i≠j，有 Ti－Tj≤1，則稱f為圖G的一個k-鄰點可區別Ⅰ-均勻全染色（簡記為k-Ⅰ-AVDETC），而稱（G）＝min｛k｜G 的k-Ⅰ-AVDETC｝為圖G的鄰點可區別Ⅰ-均勻全色數，其中 Ti＝Vi∪Ei，Vi＝｛v｜v∈V（G），f（v）＝i｝，Ei＝｛e｜e∈E（G），f（e）＝i｝.

定義 3［12］對簡單圖 G，若V（M（G））＝V（G）∪V′∪｛w｝，E（M（G））＝E（G）∪｛uv′｜u∈V（G），v′∈V′，uv∈E（G）｝∪｛wv′｜v′∈V′｝，其中V′＝｛v′｜v∈V（G）｝，｛w｝∩（V∪V′）＝，稱圖M（G）是圖G的Mycielski圖.

猜想1［9］對簡單連通圖G，有（G）≤Δ（G）＋2.

引理1［9］（G）≥Δ（G），Δ（G）表示圖G的最大度.

引理2［9］對 V（G）≥2的連通圖G，若有最大度點相鄰.

文中未加說明的符號或術語可參見文獻［13］.

2 主要結論

定理1 設Pn表示階為n（n≥3）的路，則有

證明 以下分3種情形證明本定理.

情形1 當n＝3時，Δ（M（P3））＝4，由引理1知（G）≥Δ（G），為證定理為真，只需給出M（P3）的一個4-Ⅰ-AVDETC.為此，構造映射f：V（M（P3））∪E（M（P3））→｛1，2，3，4｝，f（v1）＝f（v′1）＝f（v1v2）＝f（v3v′2）＝1；f（v2）＝f（v′2）＝f（v2v′1）＝f（v′3w）＝2； f（v3）＝f（v′3）＝f（v2v′3）＝f（v′2w）＝3；f（v2v3）＝f（v1v′2）＝f（v′1w）＝f（w）＝4.

為驗證上述全染色法f是鄰點可區別的，現列出各頂點的色集合：

C（v1）＝｛1，4｝；C（v2）＝C（v′2）＝；

C（v3）＝｛1，3，4｝；C（v′1）＝｛1，2，4｝；

C（v′3）＝｛2，3｝；C（w）＝｛2，3，4｝

可見f是M（P3）的一個4-Ⅰ-AVDTC，并且顯然有 Ti＝4，i＝1，2，3，4.

由定義知f是M（P3）的一個4-Ⅰ-AVDETC.

情形2 當n＝4時，由于M（P4）有兩個相鄰的最大度點，且Δ（M（P4））＝4.由引理2知，（M （P））≥Δ（M （P））＋1＝5，為 證44（M（P））＝5，只需給出 M（P）的一個5Ⅰ44－－AVDETC.為 此 構 造 映 射 f：V （M （P4））∪E（M（P4））→｛1，2，3，4，5｝，f（vi）＝f（v′i）＝i，i＝1，2，3，4；f（vivi＋1）＝i，i＝1，2，3；f（v′iw）＝i－1，i＝2，3，4；f（v1v′2）＝f（v3v′4）＝f（v4v′3）＝f（w）＝5；f（v2v′3）＝f（v3v′2）＝f（v′1w）＝4；f（v2v′1）＝3.

此時需驗證

C（v1）＝｛1，5｝；C（v2）＝｛5｝；C（v3）＝｛1｝；

C（v4）＝｛3，4，5｝；C（v′1）＝｛1，3，4｝；

C（v′2）＝｛3｝；C（v′3）＝｛1｝；

C（v′4）＝｛3，4，5｝；C（w）＝

從而f是M（P4）的一個5-Ⅰ-AVDTC，且有

由定義知f是 M（P4）的一個5-Ⅰ-AVDETC.

情形3 當n≥5時，M（Pn）只有一個最大度點w，由引理1知，χiaet（G）≥Δ（G）＝n.為證定理為真，只需給出 M（Pn）的一個n-Ⅰ-AVDETC，為此構造映射f：V（M（Pn））∪E（M（Pn））→｛0，1，2，…，n－1｝，f（vi）＝f（v′i）＝f（vivi＋1）＝（i＋1）mod n，i＝1，2，…，n－1；f（vn）＝1；f（v′n）＝0；f（w）＝1；f（viv′i＋1）＝（i＋2）mod n，i＝1，2，…，n－1；f（viv′i－1）＝（i＋3）mod n，i＝2，3，…，n；f（v′w）＝imod n，i＝1，2，…，n.

此時需檢驗

由定義知f 是M（Pn）（n≥5）的一個n-Ⅰ－AVDETC.

綜合以上情形，定理得證.

定理2 設Cn表示階為n（n≥3）的圈，則有

證明 以下分3種情形證明本定理.

情形1 當n＝3時，M（C3）有相鄰的最大度點，且Δ（M（C3））＝4，由引理2有χiaet（M（C3））≥Δ（M（C3））＋1＝5.為證χiaet（M（C3））＝5，只需給出M（C3）的一個5-Ⅰ-AVDETC.為此構造映射f：V（M（C3））∪E（M（C3））→｛1，2，3，4，5｝，f（v1）＝f（v1v′2）＝f（v2v′1）＝f（w）＝1；f（v2v′3）＝f（v3v′2）＝f（v′1）＝2；f（v1v′3）＝f（v2v3）＝f（v′2）＝f（v′1w）＝3；f（v3v1）＝f（v2）＝f（v′3）＝f（v′2w）＝4；f（v3）＝f（v1v2）＝f（v3v′1）＝f（v′3w）＝5.

此時需要檢驗

C（w）＝｛2｝

從而f是M（C3）的一個5-Ⅰ-AVDTC，且有

由定義知f是M（C3）的一個5-Ⅰ-AVDETC.

情形2 當n＝4時，M（C4）有相鄰的最大度點，且Δ（M（C4））＝4，由引理2知，（M（C4））≥Δ（M（C4））＋1＝5.為證（M（C4））＝5，只需給出M（C4）的一個5-Ⅰ-AVDETC.為此構造映射f：V（M（C4））∪E（M（C4））→｛1，2，3，4，5｝，f（vi）＝i，i＝1，2，3，4；f（v′i）＝5，i＝1，3，4；f（v′2）＝2；f（w）＝4；f（vivi＋1）＝i，i＝1，3；f（v2v3）＝f（v4v5）＝5；f（v1v′2）＝f（v2v′1）＝3；f（v2v′3）＝f（v3v′2）＝4；f（v3v′4）＝f（v4v′3）＝1；f（v4v′1）＝f（v1v′4）＝2；f（v′iw）＝i，i＝1，2，3，4.

此時需檢驗

從而f是M（C4）的一個5-Ⅰ-AVDTC，且有Ti＝5，i＝1，2，3，4，5.

由定義知f是M（C4）的一個5-Ⅰ-AVDETC.

情形3 當n≥5時，M（Cn）只有一個最大度點w，由引理1知，χiaet（M（Cn））≥Δ（M（Cn））＝n，為證定理為真，只需給出 M（Cn）的一個n-Ⅰ－AVDETC.由 于 V （M （Cn））＝V （M （Pn）），E（M（Cn））＝E（M （Pn））∪ ｛vnv1｝∪ ｛v1v′n｝∪｛vnv′1｝.

故若可能，可思考在定理1情形3的基礎上對 M（Pn）再添加3條邊vnv1、v1v′n、vnv′1，并對其著以適當的顏色，得到 M（Cn）的一個n-Ⅰ－AVDETC即可.為此，在定理1情形3的基礎上，令f（vnv1）＝1，f（v1v′n）＝4，f（vnv′1）＝2.再檢驗C（v1）＝｛1，2，3，4｝，C（vn）＝｛0，1，2，3｝，C（v′1）＝｛1，2，5mod n｝，C（v′n）＝｛0，1，4｝.而其他所有點的色集合未變，顯然，對任意的uv∈E（M（Cn）），有C（u）≠C（v）.

從而f為M（Cn）的一個n-Ⅰ-AVDTC.又由

由定義知f是M（Cn）的一個n-Ⅰ-AVDETC.

綜合以上情形，定理得證.

定理3 設Sn表示階為n＋1（n≥3）的星，則有

證明 由圖 M（Sn）的結構知Δ（M（Sn））＝2n，由 引 理 1 知 χiaet（M （Sn））≥2n.為 證χi（M（S））＝2n，只需給出 M（S）的一個2nⅠ

aetnn－－AVDETC.為 此 構 造 映 射 f：V （M （Sn））∪E（M（Sn））→｛1，2，…，2n｝，f（vi）＝f（v′i）＝i＋1，i＝0，1，2，…，n；f（w）＝2n；f（v0vi）＝i，i＝1，2，…，n；f（v0v′i）＝f（v′0vi）＝n＋i，i＝1，2，…，n；f（v′iw）＝i＋1，i＝0，1，2；f（v′iw）＝n＋i－1，i＝3，4，…，n.

此時需檢驗

從而f 是 M （Sn）（n≥3）的一個 2n-Ⅰ－

由定義知f是M（Sn）（n≥3）的一個2n-Ⅰ－AVDETC，可以看出猜想1對上述定理中的圖是成立的.

3 結 語

圖的鄰點可區別Ⅰ-均勻全染色是一個較新的概念，目前對于圖的鄰點可區別Ⅰ-均勻全色數的研究甚少，本文利用函數構造法，研究并確立了圖M（Pn）、M（Cn）和 M（Sn）的鄰點可區別Ⅰ-均勻全色數，驗證了鄰點可區別Ⅰ-均勻全色數對于這些特殊圖成立，具有一定的理論意義和實際意義.