兩類圖的鄰點可區別全染色

曹 蓉，林育青，童細心

（1.廣東汕頭幼兒師范高等教育?？茖W校，廣東 汕頭 515041；2.汕頭職業技術學院自然科學系，廣東 汕頭 515041）

0 引言及概念

圖的染色問題作為圖論的一個重要內容，由于它重要的理論意義和實際意義，一直是人們研究的熱點.2004年，Zhang等[1]首先提出了鄰點可區別全染色的定義，并確定了圈、完全圖、扇、輪、完全二部圖、路、樹的鄰點可區別全色數.從此鄰點可區別全染色得到了很多人的重視，但由于缺乏一個系統而有效的研究方法，至今大部分的成果都是針對一些特殊圖去探索其鄰點可區別全染色，也取得了一些研究成果[1-21].本文主要研究了輪環圖kCn和圖k×Cn的鄰點可區別全染色，得到了它們的鄰點可區別全色數.

定義1：[1]設圖G是階至少為2的連通圖，k是正整數，f是 V（G）∪E（G）到{1，2，3，…，k}的映射，對任意v∈V（G），記.如果：

（?。θ我鈛v，vw∈E（G），u≠w，有f（uv）≠f（vw）；

（ⅱ）對任意uv∈E（G），有f（u）≠f（v），f（u）≠f（uv），f（v）≠f（uv），則f稱為G的k－正常全染色.進一步，如果f還滿足：

（ⅲ）對任意 uv∈E（G），有 C（u）≠C（v），

則f稱為G的k－鄰點可區別全染色（簡記為k－AVDTC）.稱

為G的鄰點可區別全色數，記作χat（G）.

定義 2：[15]設 k1，k2，…，kn是非負整數，Cn＝v1v2…vnv1是有 n（n≥3，下同）個頂點 n 條邊的圈，則稱圖 Cn＋{v1v11，v1v12，…，v1v1k1，v2v21，…，v2v2k2，…，vnvn1，…，vnvnkn}為（k1，k2，…，kn）輪環圖，簡記為 C(k1，k2，…，kn).ki均為零時，該圖為圈 Cn；若 ki＝1，i＝1，2，…，n 時，該圖為太陽圖[16]，記為1Cn；當k1＝k2＝…＝kn＝k時，記為kCn（見圖1）.

圖1 輪環圖kCn

本文所討論的圖都是階不小于 2的無向簡單連通圖，V（G），E（G），Δ（G）和 d（v）分別表示圖G的點集合、邊集合、最大度和點v的度數，其它未加說明的定義和符號均來自文獻[22].

1 結果及證明

綜上可知，χat（kCn）＝k＋4，定理2得證.

推論1在圖kCn中，把圈Cn上每個頂點的每一條懸掛延長為長度不小于2的路Pi，j所得到的圖G，其鄰點可區別全色數仍為χat（G）＝k＋4.

證明：結合引理2和定理2，結論顯然成立.

推論2 在輪環圖C(k1，k1，…，kn)中，若圈Cn上存在相鄰的兩個頂點有相等且最大數量的懸掛，即存在k＝kj＝kj＋1＝max{k1，k2，…，kn}，則其鄰點可區別全色數仍為χat（C(k1，k1，…，kn)）＝k＋4.

證明：結合引理1和定理2，結論顯然成立.

定理3柱圖2×Cn的鄰點可區別全色數χat（2×Cn）＝5.

圖2 柱圖k×Cn

綜合情況1至情況5，當k≥3時，χat（k×Cn）＝6，從而定理4得證.

2 圖例

根據定理1給出太陽圖1C9和1C8的5－AVDTC如圖3、圖4.根據定理2，給出輪環圖3C9和4C8的（k＋4）－AVDTC如圖5、圖6.根據定理3，給出柱圖2×Cn的5－AVDTC如圖7、圖8.根據定理4，給出柱圖k×Cn的6－AVDTC如圖9、圖10、圖11、圖12和圖13.

圖3 C9的 5－AVDTC

圖4 1C8的 5－AVDTC

圖5 3C9的7－AVDTC

圖6 4C8的 8－AVDTC

圖7 2×C9的 5－AVDTC

圖8 2×C8的 5－AVDTC

圖9 5×C9的 6－AVDTC

圖10 4×C9的 6－AVDTC

圖11 5×C8的 6－AVDTC

圖12 4×C8的6－AVDTC

圖13 7×C3的6－AVDTC