兩類特殊圖的鄰和可區別全染色*

劉蒙蒙，紅 霞

（洛陽師范學院數學科學學院，河南 洛陽 471022）

1 引言

本文中所有指定的圖均為無向簡單圖，如文中沒有進行說明的圖論符號和術語同文獻[1].設G＝（V，E）是一個簡單圖，其頂點集為V＝V（G），邊集為E＝E（G）.對任意u∈V（G），NG（u）表示點u在G中的鄰集，NG[u]＝NG（u）∪{u}表示點u在G中的閉鄰集，dG（u）＝NG（u）表示點 u在 G 中的度，而 δ＝δ（G）和 Δ＝Δ（G）分別表示圖 G 的最小度和最大度.在不致混淆情況下，可將 NG（u），NG[u]，Δ（G），δ（G）分別簡單記為 N（u），N[u]，Δ，δ.

圖染色問題是圖論中很重要的研究課題之一.它涵蓋的內容比較豐富，包括頂點染色，邊染色，全染色以及延伸的多種形式的染色概念[2-4].自從張忠輔教授提出圖的鄰點可區別邊染色和鄰點可區別全染色概念之后，很多相關學者依次加入到該研究領域并展開研究.事實上，圖的鄰和可區別染色理論是圖的鄰點可區別染色的一種推廣，它具有重要的意義和研究價值[5].與鄰點可區別染色相比較，鄰和可區別染色有更加嚴格的限制條件.近幾年，與“和（Sum）”有關的染色問題的研究越來越活躍[6-8].2011年，Monika和Mariusz[9]首次提出圖的鄰和可區別全染色概念.Monika等人提出了關于圖G的鄰和可區別全染色的猜想：對每一個最大度為Δ的圖G，有成立，并給出此猜想對完全圖、圈、二分圖成立.本文主要給出兩類圖即蜘蛛圖n·Pm和圈的冠圖Ir（Cm）的鄰和可區別全染色數的精確值，從而說明了此猜想對這兩類圖是成立的.

2 基本概念

定義 1[9]設圖 G 是階數不小于 2 的連通圖，[k]＝{1，2，3，…，k}，φ 是從 V（G）∪E（G）到[k]的映射，對于任意u∈V（G），令f（u）＝∑uv∈E(G)φ（uv）＋φ（u），如果φ滿足：

（1）對于任意 uv∈E（G），有 φ（u）≠φ（v）≠φ（uv）；

（2）對于任意 uv，uw∈E（G），v≠w，有 φ（uv）≠φ（uw）.則稱 φ 為圖 G 的正常[k]-全染色.若進一步滿足：

（3）對任意的uv∈E（G），有f（u）≠f（v），則稱φ為圖G的[k]-鄰和可區別全染色，k的最小值稱為圖G的鄰和可區別全色數，記為.

定義2具有一個公共點的n條長為m－1的路Pm組成的圖，稱為蜘蛛圖，記為n·Pm（其中公共點是n條路的端點粘合而成的）.

定義3在一個圖G的每一個頂點均增加r（r≥1）條懸掛邊所得的圖，稱為圖G的r-冠圖，記為Ir（G）.1-冠圖簡稱為冠圖，記為I（G）.

引理1[9]對任意階至少為2的簡單連通圖G，有，其中 Δ（G）為圖G的最大度.

引理2[9]若階至少為2的簡單連通圖G中存在相鄰的最大度點，則

3 主要結果及證明

定理1對于蜘蛛圖n·Pm（n≥3），有

證明：令圖G＝n·Pm，其頂點集和邊集為

故此時滿足定義1，從而φ是圖G的一個[n＋1]-鄰和可區別全染色，所以.定理1證畢.

定理2對于冠圖Ir（Cn）（r≥1，n≥3），有

證明：令G＝Ir（Cn）（r≥1，n≥3），其點集和邊集為