馬寶林（河南科技學院,河南新鄉(xiāng)453003）

完全圖的點可區(qū)別V-全染色

馬寶林
（河南科技學院,河南新鄉(xiāng)453003）

根據(jù)圖的點可區(qū)別全染色的概念及其染色方法,討論了圖的點可區(qū)別V-全染色,給出了完全圖Kn的點可區(qū)別V-全色數(shù)的結論及其證明,為進一步探討其他簡單圖的點可區(qū)別V-全染色提供了理論證據(jù),豐富了圖的點可區(qū)別V-全染色的結果.

簡單圖；點可區(qū)別V-全染色；點可區(qū)別V-全色數(shù)；完全圖

圖論是一個應用十分廣泛而又極其有趣的數(shù)學分支,它的研究開始于200多年前,它的第一篇論文是1736年Euler發(fā)表的,其主要內容是利用圖論的方法解決了當時著名的格尼斯堡七橋問題.20世紀60年代以來,圖論在科學界異軍突起,活躍非凡,在解決物理學、化學、生物學、信息與計算機科學以及社會科學等諸多學科問題中,圖論已顯示出極大的優(yōu)越性.但當前對圖論研究比較活躍的兩類問題是圖的匹配問題和圖的染色問題.而全染色又是染色的一個傳統(tǒng)問題,目前已經得到很多重要的結果.2004年,在全染色的基礎上,張忠輔、陳祥恩等提出了圖的鄰點可區(qū)別全染色這一新概念[1],在圖論的染色理論中產生了新的有趣課題,并且現(xiàn)已得到了一些有價值的成果.2008年,在點可區(qū)別正常全染色的基礎上,張忠輔、陳祥恩等又提出了圖的點可區(qū)別一般全染色[2].本文將根據(jù)圖的點可區(qū)別全染色的概念及其染色方法,討論圖的點可區(qū)別V-全染色,給出完全圖Kn的點可區(qū)別V-全色數(shù)的結論及其證明.

1 相關概念

在文獻[1]和[2]中,一些簡單圖的點可區(qū)別正常全染色已被研究,并用表示了圖的點可區(qū)別全色數(shù).在其主要結論中指出,完全圖Kn的鄰點可區(qū)別全色數(shù)與點可區(qū)別全色數(shù)一致,且為：

根據(jù)定義,圖的正常全染色滿足3個條件：（v）相鄰的兩個頂點不能染相同的顏色；（e）相鄰的兩條邊不能染相同的顏色；（i）任意的點和與之關聯(lián)的邊不能染相同的顏色.上述條件中,若只滿足其中一個或兩個條件時就被稱之為圖的一般全染色.本文僅考慮只滿足（e）和（i）時的情形.

定義設G=(V,E)是一個簡單圖,k是正整數(shù),f是V(G)∪E(G)到{1,2,3,…,k}的一個映射,對圖G的一個全染色f,用C(u)表示點u和它所關聯(lián)的邊所染的顏色組成的集合,即C(u)={f(u)}∪{f(uv)|uv∈E(G)}.若對于V(G)中的任意兩點u和v,都有C(u)≠C(v),則稱f是圖G的點可區(qū)別V-全染色,簡稱為圖G的VDVT染色.

圖G的一個VDVT染色所需要的最少顏色的數(shù)目稱為圖G的點可區(qū)別V-全色數(shù),記為.

引理對于簡單圖G,令ni是度為i（δ≤i≤△）的頂點的個數(shù),若Kn存在μ-點可區(qū)別V-全染色,則有

2 完全圖的點可區(qū)別V-全染色

3 結論

本文根據(jù)圖的點可區(qū)別V-全染色的概念,給出了完全圖Kn的點可區(qū)別V-全色數(shù),并利用數(shù)學歸納法給出了完整的證明.為進一步探討其他簡單圖的點可區(qū)別V-全染色提供了思想方法,豐富了圖的點可區(qū)別全染色的結論,為解決諸如地圖染色、排課表問題、有線通訊網、無線通訊網等實際問題給出了理論依據(jù).

[1]Zhang Z F,Chen X E.On adjacent-vertex-distinguishing total coloring of graphs[J].Science in China：Ser A,2005,48（3）：289-299．

[2]陳祥恩.n-方體的點可區(qū)別全色數(shù)的漸進性態(tài)[J].西北師范大學學報：自然科學版,2005,41（5）：1-3．

[3]Zhang ZF,Qiu PX,Xu BG,etal.Vertex-distinguishing totalcoloringsofgraphs[J].ArsCombinatoria,2008（87）：33-45．

[4]張忠輔,陳祥恩,李敬文,等.關于圖的鄰點可區(qū)別全染色[J].中國科學A輯：數(shù)學,2004,34（5）：574-583．

[5]Ma B L,Chen X E,Liu J.2-distance coloringofstrong productofgraghs[J].山東大學學報,2010,45（3）：66-70.

[6]馬寶林,劉娟,陳祥恩.圖mP2與mP3的點可區(qū)別E-全染色[J].讀寫算,2010（9）：201-202.

（責任編輯：盧奇）

Vertex distinguishing V-total coloring of com p lete graphs

Ma Baolin
（Henan Instituteof Science and Technology,Xinxiang 453003,China）

According to the definition and the method of the vertex-distinguishing total coloring,the vertexdistinguishing V-total coloring of gragh is discussed,and the conclusion and proof of the vertex-distinguishing V-total chromatic number of complete graph Knare given.To further explore other simple graph vertex-distinguishing V-total coloring provides a theoretical evidence that enriched the graph vertex-distinguishing V-total coloring results.

simple graph,Vertex-distinguishing V-total coloring,Vertex-distinguishing V-total chromatic number, complete graph

O157.5

A

1008-7516（2011）05-0044-03

10.3969/j.issn.1008-7516.2011.05.011

2011-07-23

馬寶林（1978-）,男,甘肅張家川人,碩士,講師.主要從事圖論及其應用研究.