輪，扇，星和雙星的鄰點擴(kuò)展和可區(qū)別全染色

張 輝，陳祥恩，王治文

（西北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，甘肅 蘭州 730070；寧夏大學(xué)數(shù)學(xué)計算機(jī)科學(xué)學(xué)院，寧夏 銀川 750021）

0 引言及準(zhǔn)備工作

首先，Kalkowski M等人在文獻(xiàn)[1]中介紹和研究了圖的鄰和可區(qū)別一般邊染色.并且提出著名的1-2-3猜想.其次，Przybylo J和Wo nizk M在文獻(xiàn)[2]中進(jìn)一步提出了鄰和可區(qū)別一般全染色，且提出著名的1-2猜想.在文獻(xiàn)[3]中給出：每一個圖都可以用2，3對圖的點及邊賦權(quán)，使得鄰和可區(qū)別.之后，文獻(xiàn)[4]在此基礎(chǔ)上提出鄰點擴(kuò)展和可區(qū)別全染色，且得出了一些特殊圖的鄰點擴(kuò)展和可區(qū)別全染色，提出了一個猜想.在本文中我們對輪，扇，星和雙星的鄰點擴(kuò)展和可區(qū)別全染色進(jìn)行研究與討論.

圖G的一個全k-染色是指它的全體頂點及邊分配的色集合為{1，2，…，k}.

使得圖G存在NESD全k-染色中k的最小值被稱為圖G的鄰點擴(kuò)展和可區(qū)別全色數(shù)，簡記為 egndi∑（G）.

文獻(xiàn)[5]中給出輪，扇，星和雙星的概念，對n＋1階輪Wn，設(shè)其頂點集合為V（Wn），其邊集合為{vnv1}.將n＋1階輪Wn的邊vnv1刪去之后得到的就是n＋1階的扇Fn.對n＋1階星K1，n，設(shè)其頂點集合為，其邊集合為.對2n＋2 階的雙星 S2n，設(shè)其頂點集為，其邊集合為

文獻(xiàn)[4]中研究了路，圈，完全圖，樹等圖的鄰點擴(kuò)展和可區(qū)別全染色，確定了它們的鄰點擴(kuò)展和可區(qū)別全色數(shù).并提出了一個猜想.

命題1[4]設(shè)P（mm≥2）是m階的路，則

命題2[4]設(shè)Cm（m≥3）是m階的圈，則

命題 3[4]設(shè) T 是 n（n≥2）階的樹，則.

猜想1[4]設(shè)G為簡單圖，則.

引理1[4]設(shè)Kn（n≥2）是n階的完全圖，則.

1 主要結(jié)論及其證明

定理1設(shè)W（nn≥3）為n＋1階的輪，則egndi∑（Wn）＝2.

情形1n為奇數(shù)

（2）n≥5時：c（v）0＝1；c（v2i－1）＝1，1≤2i－1≤n；c（v2）i＝2，2≤2i≤n－1.除邊vn－1vn染顏色2外，其余邊均染顏色1.則每個頂點的擴(kuò)展和計算如下：；w（v1）＝7；w（v2）i＝6，2≤2i≤n－3；w（v2i－1）＝8，3≤2i－1≤n－2；w（vn－1）＝7；w（vn）＝8.

顯然w（v）i≠w（vi＋1），vivi＋1∈E（Wn）且1≤i≤n－1；w（v1）≠w（vn）.下面考慮w（v0）≠w（v）i，1≤i≤n.由于n≥5，可知，而w（v）i≤8，因此w（v0）≠w（v）i，1≤i≤n.故當(dāng)n為奇數(shù)且n≥5時，c是Wn的一個NESD全2-染色.

情形2n為偶數(shù)

c（v0）＝1；c（v2i－1）＝1，1≤2i－1≤n－1；c（v2）i＝2，2≤2i≤n.所有邊均染顏色1.則每個頂點的擴(kuò)展和計算如下：，2≤2i≤n.

顯然w（v）i≠w（vi＋1），vivi＋1∈E（Wn）且1≤i≤n－1；w（v1）≠w（vn）.下面考慮w（v0）≠w（v）i，1≤i≤n.由于n≥4，可知，而w（v）i≤8，因此，w（v0）≠w（v）i，1≤i≤n.故當(dāng)n為偶數(shù)時，c是Wn的一個NESD全2-染色.

定理2設(shè)F（nn≥3）為n＋1階的扇，則egndi∑（Fn）＝2.

情形1n為奇數(shù)

c（v）0＝1；c（v2i－）1＝1，1≤2i－1≤n；c（v2）i＝2，2≤2i≤n－1.所有邊均染顏色1.則每個頂點的擴(kuò)展和計算如下：，w（v2）i＝6，2≤2i≤n－1；w（v2i－）1＝8，3≤2i－1≤n－2；w（vn）＝5.

顯然w（v）i≠w（vi＋1），vivi＋1∈E（Fn）且1≤i≤n－1.下面考慮w（v0）≠w（v）i，1≤i≤n.假設(shè) w（v0）＝w（v1），有，即，與n為整數(shù)矛盾；假設(shè)w（v0）＝w（v2）i，3≤2i≤n－1，有，即，與n為整數(shù)矛盾；假設(shè)w（v0）＝w（v2i－1），3≤2i≤n－2，有，即，與n為整數(shù)矛盾；假設(shè)w（v0）＝w（vn），有，即，與n為整數(shù)矛盾.因此，w（v0）≠w（v）i，1≤i≤n.故當(dāng)n為奇數(shù)時，c是Fn的一個NESD全2-染色.

情形2n為偶數(shù)

c（v0）＝1；c（v2i－1）＝1，1≤2i－1≤n；c（v2）i＝2，2≤2i≤n.所有邊均染顏色1.則每個頂點的擴(kuò)展和計算如下：，3≤2i－1≤n－1；w（vn）＝4.

顯然w（v）i≠w（vi＋1），vivi＋1∈E（Fn）且1≤i≤n－1.下面考慮w（v0）≠w（v）i，1≤i≤n.由于 n≥4，可知，而w（v）i≤8，因此，w（v0）≠w（v）i，1≤i≤n.故當(dāng)n為偶數(shù)時，c是Fn的一個NESD全2-染色。

綜上可證 egndi∑（Fn）＝2.

定理3設(shè)K1，（nn≥2）為n＋1階的星，則egndi∑（K1，n）＝1.

給K1，n的頂點與邊均染顏色1.則每個頂點的擴(kuò)展和計算如下：w（v0）＝2n，w（v）i＝2，1≤i≤n.下面考慮w（v0）≠w（v）i，1≤i≤n.由于n≥2，可知w（v0）＝2n≥4，而w（v）i＝2，因此，w（v0）≠w（v）i，1≤i≤n.故c是K1，n的NESD全1-染色.

綜上可證 egndi∑（K1，n）＝1.

定理 4 設(shè) S2n為 2（n＋1）階的雙星，則 egndi∑（S2n）＝2.

除頂點u0染顏色2外，其余頂點與邊均染顏色1.則每個頂點的擴(kuò)展和計算如下：w（u）0＝2n＋2；w（u）i＝3，1≤i≤n；w（v）0＝2n＋3；w（v）j＝2，1≤j≤n.

顯然w（u0）≠w（v）0，下面考慮w（u0）≠w（u）i，1≤i≤n；w（v）0≠w（v）j，1≤j≤n.

假設(shè)w（u0）＝w（u）i，1≤i≤n，有2n＋2＝3，即，與n為整數(shù)矛盾；假設(shè)w（v0）＝w（v）j，1≤j≤n，有2n＋3＝2，即.與n為整數(shù)矛盾.因此，w（v）0≠w（u）i，1≤i≤n，w（v）0≠w（v）j，1≤j≤n.故c是S2n的NESD全2-染色.

綜上可證 egndi∑（S2n）＝2.

2 結(jié)束語

在文獻(xiàn)[4]中探討了路，圈，完全圖，樹等圖的鄰點擴(kuò)展和可區(qū)別全染色，確定了它們的鄰點擴(kuò)展和可區(qū)別全色數(shù).但沒有給出輪，扇，星和雙星的鄰點擴(kuò)展和可區(qū)別全色數(shù).本文在路與圈的鄰點擴(kuò)展和可區(qū)別全染色的基礎(chǔ)上，給出了輪，扇，星和雙星的鄰點擴(kuò)展和可區(qū)別全染色，并確定了它們的鄰點擴(kuò)展和可區(qū)別全色數(shù).另外，我們在之前也研究過兩圈之聯(lián)的鄰點擴(kuò)展和可區(qū)別全染色，并通過刪邊的方法得到了兩路之聯(lián)及路與圈的聯(lián)圖的鄰點擴(kuò)展和可區(qū)別全染色.那么，這種方法是否能夠解決兩輪之聯(lián)，兩扇之聯(lián)及輪與扇的聯(lián)圖的鄰點擴(kuò)展和可區(qū)別全染色.這就是今后需要繼續(xù)研究的課題.