輪，扇，星和雙星的鄰點擴展和可區別全染色

張 輝，陳祥恩，王治文

（西北師范大學數學與統計學院，甘肅 蘭州 730070；寧夏大學數學計算機科學學院，寧夏 銀川 750021）

0 引言及準備工作

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

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

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

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

文獻[4]中研究了路，圈，完全圖，樹等圖的鄰點擴展和可區別全染色，確定了它們的鄰點擴展和可區別全色數.并提出了一個猜想.

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

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

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

猜想1[4]設G為簡單圖，則.

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

1 主要結論及其證明

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

情形1n為奇數

（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.則每個頂點的擴展和計算如下：；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.故當n為奇數且n≥5時，c是Wn的一個NESD全2-染色.

情形2n為偶數

c（v0）＝1；c（v2i－1）＝1，1≤2i－1≤n－1；c（v2）i＝2，2≤2i≤n.所有邊均染顏色1.則每個頂點的擴展和計算如下：，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.故當n為偶數時，c是Wn的一個NESD全2-染色.

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

情形1n為奇數

c（v）0＝1；c（v2i－）1＝1，1≤2i－1≤n；c（v2）i＝2，2≤2i≤n－1.所有邊均染顏色1.則每個頂點的擴展和計算如下：，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.假設 w（v0）＝w（v1），有，即，與n為整數矛盾；假設w（v0）＝w（v2）i，3≤2i≤n－1，有，即，與n為整數矛盾；假設w（v0）＝w（v2i－1），3≤2i≤n－2，有，即，與n為整數矛盾；假設w（v0）＝w（vn），有，即，與n為整數矛盾.因此，w（v0）≠w（v）i，1≤i≤n.故當n為奇數時，c是Fn的一個NESD全2-染色.

情形2n為偶數

c（v0）＝1；c（v2i－1）＝1，1≤2i－1≤n；c（v2）i＝2，2≤2i≤n.所有邊均染顏色1.則每個頂點的擴展和計算如下：，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.故當n為偶數時，c是Fn的一個NESD全2-染色。

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

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

給K1，n的頂點與邊均染顏色1.則每個頂點的擴展和計算如下：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 設 S2n為 2（n＋1）階的雙星，則 egndi∑（S2n）＝2.

除頂點u0染顏色2外，其余頂點與邊均染顏色1.則每個頂點的擴展和計算如下：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.

假設w（u0）＝w（u）i，1≤i≤n，有2n＋2＝3，即，與n為整數矛盾；假設w（v0）＝w（v）j，1≤j≤n，有2n＋3＝2，即.與n為整數矛盾.因此，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 結束語

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