劉蒙蒙，紅 霞

（洛陽(yáng)師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院，河南 洛陽(yáng) 471022）

1 引言

本文中所有指定的圖均為無(wú)向簡(jiǎn)單圖，如文中沒(méi)有進(jìn)行說(shuō)明的圖論符號(hào)和術(shù)語(yǔ)同文獻(xiàn)[1].設(shè)G＝（V，E）是一個(gè)簡(jiǎn)單圖，其頂點(diǎn)集為V＝V（G），邊集為E＝E（G）.對(duì)任意u∈V（G），NG（u）表示點(diǎn)u在G中的鄰集，NG[u]＝NG（u）∪{u}表示點(diǎn)u在G中的閉鄰集，dG（u）＝NG（u）表示點(diǎn) u在 G 中的度，而 δ＝δ（G）和 Δ＝Δ（G）分別表示圖 G 的最小度和最大度.在不致混淆情況下，可將 NG（u），NG[u]，Δ（G），δ（G）分別簡(jiǎn)單記為 N（u），N[u]，Δ，δ.

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

2 基本概念

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

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

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

（3）對(duì)任意的uv∈E（G），有f（u）≠f（v），則稱(chēng)φ為圖G的[k]-鄰和可區(qū)別全染色，k的最小值稱(chēng)為圖G的鄰和可區(qū)別全色數(shù)，記為.

定義2具有一個(gè)公共點(diǎn)的n條長(zhǎng)為m－1的路Pm組成的圖，稱(chēng)為蜘蛛圖，記為n·Pm（其中公共點(diǎn)是n條路的端點(diǎn)粘合而成的）.

定義3在一個(gè)圖G的每一個(gè)頂點(diǎn)均增加r（r≥1）條懸掛邊所得的圖，稱(chēng)為圖G的r-冠圖，記為Ir（G）.1-冠圖簡(jiǎn)稱(chēng)為冠圖，記為I（G）.

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

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

3 主要結(jié)果及證明

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

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

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

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

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