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

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

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

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

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

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

1 相關(guān)概念

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

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

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

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

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

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

3 結(jié)論

本文根據(jù)圖的點(diǎn)可區(qū)別V-全染色的概念,給出了完全圖Kn的點(diǎn)可區(qū)別V-全色數(shù),并利用數(shù)學(xué)歸納法給出了完整的證明.為進(jìn)一步探討其他簡(jiǎn)單圖的點(diǎn)可區(qū)別V-全染色提供了思想方法,豐富了圖的點(diǎn)可區(qū)別全染色的結(jié)論,為解決諸如地圖染色、排課表問題、有線通訊網(wǎng)、無(wú)線通訊網(wǎng)等實(shí)際問題給出了理論依據(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-方體的點(diǎn)可區(qū)別全色數(shù)的漸進(jìn)性態(tài)[J].西北師范大學(xué)學(xué)報(bào)：自然科學(xué)版,2005,41（5）：1-3．

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

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

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

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

（責(zé)任編輯：盧奇）

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-）,男,甘肅張家川人,碩士,講師.主要從事圖論及其應(yīng)用研究.