圖和的Mycielski圖的鄰點(diǎn)可區(qū)別I-全染色

顧忠棟，強(qiáng)會(huì)英，魏邦魁

(蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院，甘肅蘭州 730070)

顧忠棟，強(qiáng)會(huì)英，魏邦魁

(蘭州交通大學(xué)數(shù)理與軟件工程學(xué)院，甘肅蘭州 730070)

應(yīng)用構(gòu)造染色法研究了圖和的Mycielski圖的鄰點(diǎn)可區(qū)別I-全染色，并得到了其鄰點(diǎn)可區(qū)別I-全色數(shù)，進(jìn)一步驗(yàn)證了圖的鄰點(diǎn)可區(qū)別I-全染色猜想．

k方圖；Mycielski圖；鄰點(diǎn)可區(qū)別I-全染色；鄰點(diǎn)可區(qū)別I-全色數(shù)

Noga Alon在2002年數(shù)學(xué)國際大會(huì)上作了“離散數(shù)學(xué)方法與挑戰(zhàn)”的大會(huì)報(bào)告后，圖的染色成為一個(gè)很活躍、很新穎的研究領(lǐng)域．染色理論[1]在物理、化學(xué)、新型計(jì)算機(jī)設(shè)計(jì)、計(jì)算機(jī)圖像處理、網(wǎng)絡(luò)理論、社會(huì)科學(xué)等方面有著廣泛應(yīng)用．為此，許多研究者提出了一系列染色．1993年，Burris[2]首先提出了點(diǎn)可區(qū)別邊染色概念．張忠輔等[3-5]2002年在點(diǎn)可區(qū)別邊染色的基礎(chǔ)上提出了鄰點(diǎn)可區(qū)別邊染色的概念，于 2004年提出了具有廣泛應(yīng)用背景的鄰點(diǎn)可區(qū)別全染色概念，并于2008年進(jìn)一步提出了圖的鄰點(diǎn)可區(qū)別I-全染色概念．在文獻(xiàn)[6]中楊隨義等得到了兩類3-正則Halin圖的鄰點(diǎn)可區(qū)別I-全染色．本文結(jié)合了上述研究，得到了兩類k方圖的Mycielski圖的鄰點(diǎn)可區(qū)別I-全染色．

1 相關(guān)概念和基礎(chǔ)

定義1[5]對(duì)圖G( V,E)，映射f: V( G)∪E( G)→｛1,2,···,k｝，其中k為正整數(shù)，如果f滿足：

1）對(duì)任意uv∈E( G),u≠v ，有f( u )≠f( v)；

2）對(duì)任意uv,uw∈E( G),v≠w ，有f( uv)≠f( vw) ；

3）對(duì)任意uv∈E( G),u≠v ，有C( u)≠C( v)，其中C( u)=｛f( u)｝∪｛f( uv)|uv∈E( G)｝.則稱f為圖G的鄰點(diǎn)可區(qū)別 I-全染色（簡記為k-I-AVDT ），而稱?(=mink| G 有 k-I-AVDT ｝為G的鄰點(diǎn)可區(qū)別I-全色數(shù)．其中是點(diǎn)u的色集合C( u)相對(duì)于色集合色C=｛1,2,···,k ｝的補(bǔ)集．

引理 1[6]對(duì)任意連通圖G且，則有．若圖有相鄰的最大度點(diǎn)，則，其中Δ為圖G的最大度．

猜想1[6]對(duì)于階數(shù)不小于2的簡單連通圖G，則有

定義2[7]對(duì)圖G( V,E)，M( G)稱為圖G的Mycielski圖，其中：

定義3[8]對(duì)圖G( V,E)和自然數(shù)k，若則稱圖kG 為圖G的k方圖．

本文未加說明的符號(hào)和術(shù)語參考文獻(xiàn)[9-10]．

2 主要結(jié)論和證明

定理1 設(shè) Pn是n個(gè)點(diǎn)的路（n≥4），則

下面分兩種情況證明．

情況1 4≤n≤8時(shí)，分五種情況證明：

給出它的一個(gè)6- I- AVDTC ，令f如下：

此時(shí)f的色集合如下：

給出它的一個(gè)7-I-AVDTC ，令f如下：

此時(shí)f的色集合如下：

給出它的一個(gè)8-I-AVDTC ，令f如下：

此時(shí)f的色集合如下：

給出它的一個(gè)9-I-AVDTC ，令f如下：

對(duì)于其它邊uivj有

此時(shí)f的色集合如下：

給出它的一個(gè)n-I-AVDTC ，下面分兩種情況證明：

情況2.1 當(dāng)n≡0(mod2)時(shí)，令f如下：

對(duì)于其它邊uivj有

此時(shí)f的色集合如下：

且1≤j≤n-1，C( vn)=｛1,n-2,n-4,n｝．

情況2.2 當(dāng)n≡1(mod2)時(shí)，令映射f如下：

對(duì)于其它邊uivj有

此時(shí)f的色集合如下：

且1≤j≤n-1，C( vn)=｛1,n-2,n-4,n｝．

定理2 設(shè)Cn是n個(gè)點(diǎn)的圈（n ≥ 4），則

下面分三種情況證明．

情況2 當(dāng)5≤n≤8時(shí)，分四種情況證明．

給出它的一個(gè)9-I-AVDTC ，令映射f如下：

對(duì)于其它邊uivj有

此時(shí)f的色集合如下：

給出它的一個(gè)9-I-AVDTC ，令f如下：

此時(shí)f的色集合如下：

給出它的一個(gè)9-I-AVDTC ，令f如下：

對(duì)于其它邊uivj有

此時(shí)f的色集合如下：

給出它的一個(gè)n-I-AVDTC ，分兩種情況證明：

情況3.1 當(dāng)n≡0(mod2)時(shí)，令f如下：

對(duì)于其它邊uivj有

此時(shí)f的色集合如下：

情況3.2 當(dāng)n≡1(mod2)時(shí)，令f如下：

對(duì)于其它邊uivj有

此時(shí)f的色集合如下：

綜上可知，結(jié)論成立．

[1] Bondy J A,Marty U S R. Graph theory with applications [M]. New York: The Macmillan Press Ltd,1976: 91-131.

[2] Burris A C,Schelp R H.Vertex-distinguishing proper edge-coloring [J]. J of Graph Theory,1997,26(2): 73-82.

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

[4] Zhang Z F,Chen X E,Li J W,et al. On adjacent vertex-distinguishing total coloring of graphs [J]. Science in China: Ser A Mathmatics,2005,48(3): 289-299.

[5] Zhang Z F,Woodall D R,Yao B,et al. Adjacent vertex-distinguishing I-total coloring of graphs [EB/OL]. 2008-06-12. http://202.201/18.40.8080/mas/5.

[6] 田京京．若干多重Mycielski圖的鄰點(diǎn)可區(qū)別I-全染色[J]．計(jì)算機(jī)工程與應(yīng)用（自然科學(xué)版），2012，48（25）：39-41.

[7] 孔令峰，蘇文龍，羅海鵬，等．的Mycielski圖的鄰點(diǎn)強(qiáng)邊色數(shù)和鄰點(diǎn)可區(qū)別全染色[J]．廣西科學(xué)，2008，15（1）：4-6.

[8] 楊隨義，何萬生，何建偉．兩類3-正則Halin圖的鄰點(diǎn)可區(qū)別I-全染色[J]．西南大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，33（12）：98-102.

[9] 田雙亮，李敬文，張忠輔．和的均勻鄰強(qiáng)邊色數(shù)[J]．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2006，36（3）：244-248. [10] Bondy J A,Murty U S R. Graph theory [M]. New York: New York Spring,2008: 101-110.

The Study of Adjacent Vertex-Distinguishing I-total Coloring of Mycielski Graph withand

GU Zhongdong,QIANG Huiying,WEI Bangkui
(College of Mathematics,Physics and Software Engineering,Lanzhou Jiaotong University,Lanzhou,China 730070)

The paper applies the structure staining method to study the adjacent vertex-distinguishing I-total coloring of Mycielski graph ofand. And the adjacent vertex-distinguishing I-total chromatic of Mycielski graph ofandis obtained thereby. The conjecture of the adjacent vertex-distinguishing I-total coloring graph is further verified in this paper.

K-square Graph; Mycielski Graph; Adjacent Vertex-distinguishing I-total Coloring; Adjacent Vertex-distinguishing I-total Chromatic Number

O157.5

：A

：1674-3563(2017)01-0030-09

10.3875/j.issn.1674-3563.2017.01.004 本文的PDF文件可以從xuebao.wzu.edu.cn獲得

(編輯：封毅)

2015-09-24

國家自然科學(xué)基金(11401038)

顧忠棟(1990- )，男，甘肅武威人，碩士研究生，研究方向：圖論與組合優(yōu)化