若干Mycielski圖鄰點(diǎn)可區(qū)別Ⅰ-均勻全染色

張 婷＊1， 朱 恩 強(qiáng)， 趙 雙 柱， 杜 佳

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

0 引 言

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

1 相關(guān)定義和引理

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

（1）對(duì)uv∈E（G），u≠v，有f（u）≠f（v）；

（2）對(duì) uv，uw∈E（G），v≠w，f（uv）≠f（uw）；

（3）對(duì)uv∈E（G），u≠v，C（u）≠C（v）則稱f為圖G的一個(gè)鄰點(diǎn)可區(qū)別的Ⅰ-全染色（簡(jiǎn)記為k-Ⅰ-AVDTC）.記χiat（G）＝min｛k｜G 的k-Ⅰ-AVDTC｝為圖G的鄰點(diǎn)可區(qū)別Ⅰ-全色數(shù).其中C（u）＝｛f（u）｝∪｛f（uv）｜uv∈E（G）｝稱為點(diǎn)u在f下的色集，C（u）在色全集合C＝｛1，2，…，k｝中的補(bǔ)集記為C（v）＝C＼C（u）.

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

定義 3［12］對(duì)簡(jiǎn)單圖 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］對(duì)簡(jiǎn)單連通圖G，有（G）≤Δ（G）＋2.

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

引理2［9］對(duì) V（G）≥2的連通圖G，若有最大度點(diǎn)相鄰.

文中未加說(shuō)明的符號(hào)或術(shù)語(yǔ)可參見(jiàn)文獻(xiàn)［13］.

2 主要結(jié)論

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

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

情形1 當(dāng)n＝3時(shí)，Δ（M（P3））＝4，由引理1知（G）≥Δ（G），為證定理為真，只需給出M（P3）的一個(gè)4-Ⅰ-AVDETC.為此，構(gòu)造映射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.

為驗(yàn)證上述全染色法f是鄰點(diǎn)可區(qū)別的，現(xiàn)列出各頂點(diǎn)的色集合：

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｝

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

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

情形2 當(dāng)n＝4時(shí)，由于M（P4）有兩個(gè)相鄰的最大度點(diǎn)，且Δ（M（P4））＝4.由引理2知，（M （P））≥Δ（M （P））＋1＝5，為 證44（M（P））＝5，只需給出 M（P）的一個(gè)5Ⅰ44－－AVDETC.為 此 構(gòu) 造 映 射 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.

此時(shí)需驗(yàn)證

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）的一個(gè)5-Ⅰ-AVDTC，且有

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

情形3 當(dāng)n≥5時(shí)，M（Pn）只有一個(gè)最大度點(diǎn)w，由引理1知，χiaet（G）≥Δ（G）＝n.為證定理為真，只需給出 M（Pn）的一個(gè)n-Ⅰ-AVDETC，為此構(gòu)造映射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.

此時(shí)需檢驗(yàn)

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

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

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

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

情形1 當(dāng)n＝3時(shí)，M（C3）有相鄰的最大度點(diǎn)，且Δ（M（C3））＝4，由引理2有χiaet（M（C3））≥Δ（M（C3））＋1＝5.為證χiaet（M（C3））＝5，只需給出M（C3）的一個(gè)5-Ⅰ-AVDETC.為此構(gòu)造映射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.

此時(shí)需要檢驗(yàn)

C（w）＝｛2｝

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

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

情形2 當(dāng)n＝4時(shí)，M（C4）有相鄰的最大度點(diǎn)，且Δ（M（C4））＝4，由引理2知，（M（C4））≥Δ（M（C4））＋1＝5.為證（M（C4））＝5，只需給出M（C4）的一個(gè)5-Ⅰ-AVDETC.為此構(gòu)造映射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.

此時(shí)需檢驗(yàn)

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

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

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

故若可能，可思考在定理1情形3的基礎(chǔ)上對(duì) M（Pn）再添加3條邊vnv1、v1v′n、vnv′1，并對(duì)其著以適當(dāng)?shù)念伾玫?M（Cn）的一個(gè)n-Ⅰ－AVDETC即可.為此，在定理1情形3的基礎(chǔ)上，令f（vnv1）＝1，f（v1v′n）＝4，f（vnv′1）＝2.再檢驗(yàn)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｝.而其他所有點(diǎn)的色集合未變，顯然，對(duì)任意的uv∈E（M（Cn）），有C（u）≠C（v）.

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

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

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

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

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

aetnn－－AVDETC.為 此 構(gòu) 造 映 射 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.

此時(shí)需檢驗(yàn)

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

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

3 結(jié) 語(yǔ)

圖的鄰點(diǎn)可區(qū)別Ⅰ-均勻全染色是一個(gè)較新的概念，目前對(duì)于圖的鄰點(diǎn)可區(qū)別Ⅰ-均勻全色數(shù)的研究甚少，本文利用函數(shù)構(gòu)造法，研究并確立了圖M（Pn）、M（Cn）和 M（Sn）的鄰點(diǎn)可區(qū)別Ⅰ-均勻全色數(shù)，驗(yàn)證了鄰點(diǎn)可區(qū)別Ⅰ-均勻全色數(shù)對(duì)于這些特殊圖成立，具有一定的理論意義和實(shí)際意義.