蔡學(xué)鵬，任佰通，馮苗苗

?

圖的鄰點(diǎn)強(qiáng)可區(qū)別V-全色數(shù)的一個(gè)上界

*蔡學(xué)鵬，任佰通，馮苗苗

（新疆農(nóng)業(yè)大學(xué)數(shù)理學(xué)院，新疆，烏魯木齊830052）

應(yīng)用概率論中的Lovasz一般局部引理得出了圖的鄰點(diǎn)強(qiáng)可區(qū)別V-全色數(shù)的上界，證明了對(duì)階數(shù)不小于3且不含孤立邊的簡(jiǎn)單圖的鄰點(diǎn)強(qiáng)可區(qū)別V-全色數(shù)不超過(guò)49△，△≥5。

Lovasz一般局部引理；鄰點(diǎn)強(qiáng)可區(qū)別全染色；鄰點(diǎn)強(qiáng)可區(qū)別V-全染色

0 引言

隨著計(jì)算機(jī)的飛速發(fā)展，信息化和數(shù)字化技術(shù)的不斷進(jìn)步，許多實(shí)際問(wèn)題的數(shù)學(xué)模型使離散型結(jié)構(gòu)上的數(shù)字化技術(shù)得到了更多人的關(guān)注。圖的染色理論[1]作為離散數(shù)學(xué)的一個(gè)重要組成部分，自然得到了快速發(fā)展，因此受到了國(guó)際數(shù)學(xué)界與工程界越來(lái)越廣泛的重視。Noga Alon在2002年數(shù)學(xué)國(guó)際大會(huì)上作了“離散數(shù)學(xué)方法與挑戰(zhàn)”的大會(huì)報(bào)告后，圖的染色成為一個(gè)很活躍、很新穎的研究鄰域。1993年A.C.Burris在他的博士論文中提到了點(diǎn)可區(qū)別正常邊染色(也稱(chēng)強(qiáng)邊染色)的概念[2]，此后P.N.Balister等人撰文[3]對(duì)該問(wèn)題進(jìn)行了深入的討論，有關(guān)許多深入的結(jié)果都在國(guó)際權(quán)威雜志上刊出。在無(wú)線通訊網(wǎng)絡(luò)中，為了防止網(wǎng)絡(luò)中不同的長(zhǎng)點(diǎn)之間信號(hào)頻率的共振，必須保證不同站點(diǎn)之間擁有不同的通訊頻率，無(wú)線傳感器網(wǎng)絡(luò)中相鄰點(diǎn)通信沖突問(wèn)題；交通運(yùn)輸中危險(xiǎn)品運(yùn)輸?shù)呐渌驼{(diào)度安全問(wèn)題等，為了解決此問(wèn)題，張忠輔教授首次提出了鄰點(diǎn)可區(qū)別正常邊染色[4]的概念，這一問(wèn)題與點(diǎn)可區(qū)別邊染色的研究具有相同的難度，因此國(guó)內(nèi)外專(zhuān)家對(duì)此問(wèn)題作了大量研究。2004年張忠輔教授在鄰點(diǎn)可區(qū)別正常邊染色的基礎(chǔ)上提出了鄰點(diǎn)可區(qū)別全染色[5]的概念，2007年又提出了鄰點(diǎn)強(qiáng)可區(qū)別全染色[6]的概念。2010年程輝等在鄰點(diǎn)強(qiáng)可區(qū)別的基礎(chǔ)上提出了鄰點(diǎn)強(qiáng)可區(qū)別EI-全染色[7]和鄰點(diǎn)強(qiáng)可區(qū)別V-全染色[8]的概念。

圖染色理論中對(duì)于常見(jiàn)的特殊圖，如路圖、圈圖、星圖、扇圖和輪圖等，其染色數(shù)可以根據(jù)群染法、反證法和構(gòu)造函數(shù)等方法得出確定的結(jié)果。對(duì)于一般圖而言，上述方法卻不再合理。而應(yīng)用概率論中的Lovasz一般局部引理，可以很巧妙地得出一些不同類(lèi)型的圖染色的上界，該方法在文獻(xiàn)[12-15]中有一些應(yīng)用結(jié)果。本文在鄰點(diǎn)強(qiáng)可區(qū)別全染色的概念中，弱化其中的一個(gè)條件，即相鄰點(diǎn)可以染同色，從而得出了圖的鄰點(diǎn)強(qiáng)可區(qū)別V-全色數(shù)的上界。

1 預(yù)備知識(shí)

為的鄰點(diǎn)強(qiáng)可區(qū)別全色數(shù)。

為的鄰點(diǎn)強(qiáng)可區(qū)別V-全色數(shù)。該定義將定義1中的條件1)弱化了，即相鄰點(diǎn)可以染同色。

2 主要結(jié)論

1) 邊染色是正常的，既沒(méi)有兩條相鄰的邊染成同色；

2) 點(diǎn)和邊的染色是正常的，即任意一條邊與他的懸掛點(diǎn)染不同顏色；

3) 色集合是正常的，即任意相鄰兩點(diǎn)的色集合不同，這里的色集合為該點(diǎn)的顏色，與他關(guān)聯(lián)邊的顏色，以及與他相鄰點(diǎn)的顏色所組成的集合。下面將分三步完成該定理的證明。

第一步：定義以下三種類(lèi)型的壞事件

如果壞事件1，2，3不發(fā)生的概率為正，即說(shuō)明壞事件不發(fā)生是可能的，則稱(chēng)上述條件是滿(mǎn)足的，即存在鄰點(diǎn)強(qiáng)可區(qū)別-全染色。下面計(jì)算每一個(gè)壞事件發(fā)生的概率：

由二項(xiàng)式定理知，

故

第二步：構(gòu)造相關(guān)圖并計(jì)算相關(guān)事件數(shù)

表1 相關(guān)圖R

第三步：構(gòu)造常數(shù)證明以下三個(gè)不等式成立

證明(4)式只需證：

同理對(duì)于(2)式有：

同理對(duì)于(3)式有：

綜上所述，取

[1] Bondy J A, Marty USR. Graph Theory with Application[M]. New York: The Macmillan Press Ltd, 1976.

[2] Burris A C, Schelp R H. Vertex-Distinguishing Proper Edge-Coloring[J]. J of Graph Theory, 1997, 26(2):73-82.

[3] Balister P N, Riordan O M, Schelp R H. Vertex‐distinguishing edge colorings of graphs[J]. Journal of graph theory, 2003, 42(2): 95-109.

[4] Zhang Z, Liu L, Wang J. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15(5): 623-626.

[5] Zhang Z, Chen X, Li J, et al. On adjacent- vertex-distinguishing total coloring of graphs[J]. Science in China Series A: Mathematics, 2005, 48(3): 289-299.

[6] 張忠輔,程輝,姚兵,等. 圖的鄰點(diǎn)強(qiáng)可區(qū)別全染色[J].中國(guó)科學(xué)(A輯),2007, 37(9):1073-1082.

[7] Cheng H, Wang Z. Adjacent vertex strongly distinguishing EI-total coloring of graphs[J].Shandong Univ.Nat.Sci.2010(3):289-299.

[8] 程輝,謝雁. 圖的鄰點(diǎn)強(qiáng)可區(qū)別VI-全染色[J].蘭州大學(xué)學(xué)報(bào):自然科學(xué)版, 2010,46(6): 97-101.

[9] 安明強(qiáng). 點(diǎn)可區(qū)別全色數(shù)的一個(gè)上界[J].天津科技大學(xué)學(xué)報(bào), 2009, 24(5):68-70.

[10] Michael M, Bruce R. Graph coloring and the probabilistic method[M]. New York :Springer, 2002: 1329-1356.

[11] Alon N, Spencer J H. The Probabilistic Method[M]. New York:John Wiley &Sons, 1992.

[12] 晁福剛,張忠輔,強(qiáng)會(huì)英. 圖的鄰點(diǎn)可區(qū)別全色數(shù)的一個(gè)上界[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(1):91-95.

[13] 強(qiáng)會(huì)英,李沐春,張忠輔,等. 距離限制下的點(diǎn)可區(qū)別全色數(shù)的一個(gè)上界[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),2011, 34(3):554-559.

[14] 強(qiáng)會(huì)英,王洪申. 圖的鄰點(diǎn)強(qiáng)可區(qū)別全色數(shù)的一個(gè)上界[J].數(shù)學(xué)進(jìn)展, 2013, 42(6):801-805.

[15] 崔俊峰. 圖的點(diǎn)可區(qū)別邊色數(shù)的一個(gè)上界[J].首都師范大學(xué)學(xué)報(bào):自然科學(xué)版,2017, 38(1):6-8.

AN UPPER BOUND OF THE ADJACENT-VERTEX-STRONGLY-DISTINGUISHING V-TOTAL CHROMATIC NUMBERS OF GRAPHS

*CAI Xue-peng, REN Bai-tong, FENG Miao-miao

(College of Mathematics and Physics, Xinjiang Agricultural University, Urumqi, Xinjiang 830052, China)

An upper bound for adjacent-vertex-strongly-distinguishing V-total chromatic numbers is obtained by Lovasz local lemma of probability method. We show that adjacent vertex strongly distinguishing V-total chromatic numbers of graph G is not more than 49△for△≥5, where G is a simple graph with no isolated edge and the order not less than three.

Lovasz local lemma; the adjacent-vertex-strongly-distinguishing total coloring; the adjacent-vertex-strongly-distinguishing V-total coloring

1674-8085(2018)03-0005-04

O157.5

A

10.3969/j.issn.1674-8085.2018.03.002

2018-03-09；

2018-04-16

*蔡學(xué)鵬(1991-)，男，甘肅武威人，助教，碩士，主要從事圖與網(wǎng)絡(luò)優(yōu)化研究(Email:522916724@qq.com);

任佰通(1997-)，男，重慶人，新疆農(nóng)業(yè)大學(xué)數(shù)理學(xué)院本科生(Email:3212989741@qq.com);

馮苗苗(1999-)，女，重慶人，新疆農(nóng)業(yè)大學(xué)數(shù)理學(xué)院本科生(Email:2955398005@qq.com).