T-型六角系統(tǒng)的鄰點(diǎn)可區(qū)別I-全色數(shù)

楊隨義

（天水師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 天水 741001）

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

圖染色作為圖論研究的重要方向之一，被廣泛應(yīng)用于信息計(jì)算科學(xué)、通信網(wǎng)絡(luò)、交通運(yùn)輸?shù)阮I(lǐng)域，為實(shí)際問題的解決提供了重要的理論依據(jù)和最優(yōu)策略.圖染色最早起源于四色問題的研究，隨后一系列經(jīng)典染色如點(diǎn)染色、邊染色以及全染色等相繼被提出.[1]點(diǎn)染色是若干種顏色在頂點(diǎn)（邊）上的一個(gè)分配，且相鄰頂點(diǎn)（邊）分配不同的顏色，將所用的最少顏色數(shù)稱為點(diǎn)（邊）色數(shù).圖的全染色是若干種顏色同時(shí)在頂點(diǎn)和邊上的一個(gè)分配，且滿足相鄰頂點(diǎn)與相鄰邊以及關(guān)聯(lián)元素分配不同的顏色，類似地，將所用的最少顏色數(shù)稱為全色數(shù).1941年，Brooks證明任意一個(gè)既不是奇圈也不是完全圖的連通圖，其點(diǎn)色數(shù)不超過Δ.1964年前后，Vizing和Gupta分別獨(dú)立證明了任意一個(gè)圖的邊色數(shù)不超過Δ+1.此外，Vizing還猜測(cè)：任意一個(gè)圖的全色數(shù)不超過Δ+2，即后來眾所周知的全染色猜想（TCC）.染色問題已被證明是一個(gè)NP-難問題，因此，為了進(jìn)一步探索TCC猜想，國(guó)內(nèi)外學(xué)者隨后又相繼提出了一系列可區(qū)別染色.2005年，張忠輔等[1]提出了圖的鄰點(diǎn)可區(qū)別全染色的概念，并給出了圈、完全圖、完全二部圖等一些特殊圖類的鄰點(diǎn)可區(qū)別全色數(shù)，并猜測(cè)圖的鄰點(diǎn)可區(qū)別全色數(shù)Δ+2.此后，國(guó)內(nèi)外學(xué)者針對(duì)這一猜想展開了研究.[2，3]為了推動(dòng)鄰點(diǎn)可區(qū)別全色數(shù)猜想的研究，張忠輔等[4]在鄰點(diǎn)可區(qū)別全染色的基礎(chǔ)上，提出了鄰點(diǎn)可區(qū)別I-全染色的概念.隨后王繼順[4,5]研究了蛛網(wǎng)圖、漁網(wǎng)圖以及聯(lián)圖Pm∨Fn及Pm∨Wn[6]的鄰點(diǎn)可區(qū)別I-全染色.張婷、趙慧霞等[7]給出了圖C5∨Wn的鄰點(diǎn)可區(qū)別I-全色數(shù).

六角系統(tǒng)作為化學(xué)圖論中重要的研究對(duì)象，受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注.六角系統(tǒng)圖是由正六邊形所組成的平面圖網(wǎng)絡(luò)，其構(gòu)型多種多樣，不同的構(gòu)型其化學(xué)性質(zhì)也各不相同.T-型六角系統(tǒng)是一類特殊的六角系統(tǒng)，它是由一個(gè)正六邊形中心分別向3個(gè)間隔方向延伸n個(gè)正六邊形直鏈所構(gòu)成的對(duì)稱圖，簡(jiǎn)稱n階T-型六角系統(tǒng)鏈.最近，王文杰等[8]首先研究了T-型六角系統(tǒng)鏈的點(diǎn)可區(qū)別邊染色.本文以此為動(dòng)機(jī)，研究了T-型六角系統(tǒng)Tn的鄰點(diǎn)可區(qū)別I-全色數(shù)，并得到了其鄰點(diǎn)可區(qū)別I-全色數(shù).

定義1.1[1]設(shè)G是階至少為2的連通圖，k是正整數(shù)，f是V(G)?E(G)到{1,2,…,k}的映射，對(duì)任意u∈V(G)，記C(u)={f(u)}?{f(uv)|uv∈E(G),v∈V(G)}.如果

(1)對(duì)于任意uv,vw∈E(G),u≠w，有

f(uv)≠f(vw)；

(2)對(duì)于任意uv∈E(G),有

f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)；

則稱f為G的k-正常全染色，進(jìn)一步，如果f還滿足

2 主要結(jié)果