梯圖的鄰點可區(qū)別均勻I-全染色

王繼順， 左 林， 李步軍

(1. 連云港師范高等?？茖W(xué)校數(shù)學(xué)與信息工程學(xué)院， 江蘇 連云港 222006；2. 淮海工學(xué)院 數(shù)理科學(xué)系， 江蘇 連云港 222005)

1 基本概念與引理

圖的染色理論被廣泛應(yīng)用于如網(wǎng)絡(luò)優(yōu)化和信息技術(shù)等領(lǐng)域中， 用來解決實際問題． 因此， 其理論及應(yīng)用成為圖論工作者研究的重要課題． 為滿足應(yīng)用的需要， 圖的新染色方法被不斷提出[1-4]，ZhangZhongfu等[3]提出圖的鄰點可區(qū)別I-全染色概念，王繼順等[4]提出了鄰點可區(qū)別I-均勻全染色的概念，由于其都是NP完全問題，受到圖論學(xué)者的普遍關(guān)注，楊隨義等[5]研究了冠圖的鄰點可區(qū)別I-全染色，王繼順研究了蛛網(wǎng)圖、漁網(wǎng)圖[6]以及聯(lián)圖Pm∨Fn和Pm∨Wn[7]的鄰點可區(qū)別I-全染色， 劉秀麗[8]研究了某些Mycielski圖的鄰點可區(qū)別I-全染色， 王笑妍等[9]研究了風(fēng)車圖、 齒輪圖等圖的均勻鄰點可區(qū)別I-全染色， 給出了這些圖的鄰點可區(qū)別I-全色數(shù)或鄰點可區(qū)別均勻I-全色數(shù)．

定義1[3]設(shè)G(V,E)是階數(shù)至少為2的簡單連通圖, 令T(G)=V(G)∪E(G), 若存在一個正整數(shù)k和映射f∶T(G)→{1, 2, 3,…,k}, 使得

1) 對 ?uv∈E(G),u≠v, 有f(u)≠f(v);

2) 對?uv,uw∈E(G),v≠w,有f(uv)≠f(uw);

3) 對?uv∈E(G),u≠v,有C(u)≠C(v);

則稱f為G的一個鄰點可區(qū)別I-全染色 (簡記為k-I-AVDTC). 而稱

定義2[4]設(shè)f是簡單連通圖G(V,E) (|V(G)|≥2)的一個k-I-AVDTC, 若滿足對?i,j∈{1,2,…,k},i≠j， 有

||Ti|-|Tj||≤1,

則稱f為G的一個k-鄰點可區(qū)別均勻I-全染色 (簡記為k-I-AVDETC). 而稱

為G的鄰點可區(qū)別均勻I-全色數(shù), 其中Ti=Vi∪Ei,Vi={v|v∈V(G),f(v)=i},Ei={e|e∈E(G),f(e)=i}.

由上述定義, 顯然有

(1)

式中： Δ(G)表示G的最大度數(shù).

引理1[4]對|V(G)|≥2的連通圖G, 若有最大度點相鄰, 則

(2)

猜想[4]設(shè)簡單連通圖為G(V,E), 則

(3)

易見梯圖Ln與笛卡兒積圖P2×Pn是同構(gòu)的圖， 即Ln?P2×Pn.

梯圖是一種重要的網(wǎng)絡(luò)圖， 圖論學(xué)者包世堂、 張薇、 王治文等研究了它的點可區(qū)別的全染色[10-13]， 本文將研究梯圖Ln的鄰點可區(qū)別均勻I-全染色問題, 通過分析該類圖的結(jié)構(gòu)特點, 運用所構(gòu)造的有序顏色組循環(huán)對邊和點染色， 并輔以色調(diào)整技術(shù)， 給出這類圖的鄰點可區(qū)別均勻I-全染色法， 并最終得到它們的鄰點可區(qū)別均勻I-全染色數(shù).

2 主要結(jié)果與證明

定理1設(shè)梯圖Ln(n≥2), 則

(4)

情形2.1當(dāng)n≡0(mod 4)時, 對Ln進(jìn)行循環(huán)染色， 構(gòu)造從T(Ln)到{1, 2, 3, 4}的染色法f. 對頂點v1k(k=1,2,…,n)染色是用色1,2,3的有序染色組染過i=1, 2,3的頂點后， 循環(huán)向后染i直到n的頂點， 而對頂點v2k(k=1,2,…,n)的染色就是把對v1k(k=1,2,…,n)染色的染色組(1，2，3)輪換為有序染色組(2,3,1)， 然后循環(huán)向后染色. 對頂點的染色可歸納為

對Ln的邊也作循環(huán)染色， 先對邊v1kv1(k+1)(k=1,2,…,n-1)用一組有序染色組(1,2,3)染過k=1, 2,3的邊后， 循環(huán)向后染i直到n-1的邊， 而對邊v2kv2(k+1)(k=1,2,…,n-1)的染色就是把對v1iv1(i+1)(i=1,2,…,n-1)染色的有序染色組(1，2，3)輪換為有序染色組(2,3,1)， 然后循環(huán)向后染色； 對所有的邊v1kv2k(k=1,2,…,n)都染以色4. 對邊染色可歸納為

k=1,2,…,n-1;

k=1,2,…,n-1;

f(v1kv2k)=4,k=1,2,…,n.

易見, 該染色法f滿足定義1， 即是Ln(n≡0(mod 4))的一個4-I-AVDTC， 并且n=4時，f已是Ln的一個4-I-AVDETC， 但當(dāng)n>4時， 它還不是均勻的， 為此對邊或頂點的染色進(jìn)行個別調(diào)整. 這里， 只要把頂點v2(n-1)的染色由原來的2重新定義為4即可， 即令f(v2(n-1))=4. 此時， 各頂點的染色集合為

C(v11)={1,4}，;

C(v21)={2,4};

k=2,3,…,n.

不同色所染元素數(shù)為

從而, 所給染色法f是Ln當(dāng)n≡0(mod 4)時的一個4-I-AVDETC.

情形2.2當(dāng)n≡1(mod 4)時, 對Ln進(jìn)行循環(huán)染色， 構(gòu)造從T(Ln)到{1,2,3,4}的染色法f. 按照n≡0(mod 4)的染色方法f來染n≡1(mod 4)時的Ln， 只需要調(diào)整染色， 當(dāng)n=5時， 令f(v2(n-1)v2n)=3， 當(dāng)n>5時令f(v1(n-1))=4即可. 但為了盡量少做調(diào)整， 下面改換一個染色方法f. 對Ln的頂點v1k(k=1,2,…,n)用有序染色組(1,2,3,4)染過i=1,2,3,4的頂點后， 循環(huán)向后染i直到n的頂點， 而對頂點v2k(k=1,2,…,n)的染色就是把對v1k(k=1,2,…,n)染色的有序染色組(1，2，3，4)輪換為有序染色組(2,3,4,1)， 然后循環(huán)向后染色. 對頂點染色可歸納為

對Ln的邊也作循環(huán)染色， 先對邊v1kv1(k+1)(k=1,2,…,n-1)染色， 用一組有序染色組(1,2,3,4)染過k=1, 2,3,4的邊后， 循環(huán)向后染i直到n-1的邊， 而對邊v2kv2(k+1)(k=1,2,…,n-1)的染色就是把對v1iv1(i+1)(i=1,2,…,n-1)染色的有序染色組(1，2，3，4)輪換為有序染色組(2,3,4,1)， 然后循環(huán)向后染色； 將有序數(shù)組再作一次輪換得到(3,4,1,2)對所有的邊v1kv2k對k=1,2,…,n的循環(huán)染色. 對邊染色可歸納為

k=1,2,…,n-1；

k=1,2,…,n-1；

k=1,2,…,n.

上述所給出的染色法f不用做顏色調(diào)整即滿足定義2， 這是因為各頂點的染色集合為

C(v11)={1,3}；

k=2,3,…,n;

C(v21)={2,3}；

k=2,3,…,n.

不同色的染色集合為

從而根據(jù)定義2, 該染色法f是Ln當(dāng)n≡1(mod 4) 時的一個4-I-AVDETC.

情形2.3當(dāng)n≡2(mod 4)時, 對Ln進(jìn)行循環(huán)染色， 構(gòu)造從T(Ln)到{1, 2, 3, 4}的染色法f. 按照n≡1(mod 4)的染色法f來染n≡2(mod 4)時的Ln， 只需要調(diào)整v1n的染色， 重新令f(v1n)=4即可. 此時， 各頂點的染色集合規(guī)律不變， 滿足定義1， 而不同色所染元素數(shù)為

所以, 此染色法f是Ln當(dāng)n≡2(mod 4)時的一個4-I-AVDETC.

情形2.4當(dāng)n≡3(mod 4)時, 對Ln進(jìn)行循環(huán)染色， 構(gòu)造從T(Ln)到{1, 2, 3, 4}的染色法f. 同樣按照n≡1(mod 4)的染色方法f來染n≡3(mod 4)時的Ln， 只需要調(diào)整v1(n-1)的染色， 重新令f(v1(n-1))=4即可.此時各頂點的染色集合規(guī)律不變， 滿足定義1， 而不同色所染元素數(shù)為

所以, 此染色法f是Ln當(dāng)n≡3(mod 4)時的一個4-I-AVDETC.

3 結(jié) 論

運用所構(gòu)造的有序顏色組和其置換循環(huán)對邊和點染色， 并輔以色調(diào)整技術(shù)， 給出了梯圖Ln圖的鄰點可區(qū)別均勻I-全染色法， 并最終得到它們的鄰點可區(qū)別均勻I-全染色數(shù). 由于Ln?P2×Pn， 后續(xù)工作將研究能否將該種方法對更一般的笛卡爾積圖Pm×Pn進(jìn)行鄰點可區(qū)別均勻I-全染色， 從而有效確定該類圖的鄰點可區(qū)別均勻I-全色數(shù).