張 琛， 王欣欣

(隴東學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 慶陽(yáng)745000)

2004 年，在全染色的基礎(chǔ)上，張忠輔，陳祥恩等［1］提出了圖的鄰點(diǎn)可區(qū)別全染色這一新概念，得到了一些有價(jià)值的成果，并根據(jù)這些結(jié)果提出了一個(gè)猜想:對(duì)于階數(shù)不小于2 的簡(jiǎn)單連通圖，其鄰點(diǎn)可區(qū)別全色數(shù)不超過(guò)最大度加3.要完全證明這一結(jié)論較為困難，但目前已有的結(jié)果中，該猜想均成立.本文中所討論的相鄰奇數(shù)階完全圖的直積圖的鄰點(diǎn)可區(qū)別全色數(shù)也不超過(guò)這一上界.

1 定義及引理

本文所考慮的圖均為連通、有限、無(wú)向的簡(jiǎn)單圖.Δ(G)，d(v)分別表示圖G 的最大度和圖G 中頂點(diǎn)v 的度.其它術(shù)語(yǔ)及符號(hào)參［2］.

定義1 對(duì)圖G(V(G)，E(G))，t 是正整數(shù)，S是t 元集，f 是從V(G)∪E(G)到S 的映射. 如果

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(uv)≠f(v)，

3)對(duì)?uv ∈E(G)，有Cf(u)≠Cf(v)，這里Cf(u)= {f(u)}∪{f(uv)| uv ∈E(G)}叫做點(diǎn)u在f 下的顏色集合，且記ˉCf(u)= S -C(u)，則f 叫做圖G 的t -鄰點(diǎn)可區(qū)別全染色. 簡(jiǎn)稱(chēng)t -AVDTC.χat(G)= min{t| G 有t -AVDTC}叫做圖G 的鄰點(diǎn)可區(qū)別全色數(shù).

定義2 對(duì)圖G1= (V1，E1)和G2= (V2，E2)，直積圖G1× G2的頂點(diǎn)集為V × V2，點(diǎn)(u1，v1)與(u2，v2)相鄰當(dāng)且僅當(dāng)u1u2∈E1，v1= v2∈V2或者u1= u2∈V1，v1v2∈E2.

顯然有G1× G2≌G2× G1，Δ(G1× G2)=Δ(G1)+ Δ(G2).

定義3 如果圖G 的一個(gè)邊子集M 中，每條邊的兩個(gè)端點(diǎn)不同，且任兩邊在G 中不相鄰，則稱(chēng)M為圖G 的一個(gè)匹配.

引理1［1］如果圖G 有兩個(gè)相鄰的最大度點(diǎn)，則χat(G)≥Δ(G)+2.

引理2［1］Kn是n(n ≥3)階完全圖，則

其中χt(Kn)為Kn的全色數(shù).

引理3［3］Kn是n(n ≥3)階完全圖，則

其中χas'(Kn)為Kn的鄰強(qiáng)邊色數(shù).

本文給出了相鄰奇數(shù)階完全圖的直積圖K2n-1× K2n+1' 的鄰點(diǎn)可區(qū)別全色數(shù).

2 主要結(jié)果

定理1 對(duì)于相鄰奇數(shù)階完全圖的直積圖K2n-1× K2n+1'(n 為正整數(shù))，則

證明 在K2n-1× K2n+1'中，記vij= (ui，uj')，用K2n+1' 表示頂點(diǎn)集為V(K'(i)2n+1)= {vi1，vi2，…，vi，(2n+1)}的2n +1 階完全圖，用K2n-1表示頂點(diǎn)集為的2n - 1 階完全圖.

由定義2 知，K2n-1× K2n+1' 是兩個(gè)邊不交的子圖與的并集.即

顯然K2n-1× K2n+1' 為正則圖，且χat(K2n-1×K2n+1')= 4n -2，由引理1，χat(K2n-1×K2n+1')≥4n.下僅需證明K2n-1× K2n+1'存在4n - AVDTC 即可.

可分三步定義一個(gè)從E(K2n-1× K2n+1')∪V(K2n-1× K2n+1')到色集{a0，a1，…，a2n，b0，b1，…，b2n-2}的映射f.

其中下標(biāo)p + q 與p - q 取模2n +1.

顯 然，Ti1，Ti2，…，Ti2n+1是 E(K2n+1') ∪V(K2n+1')的一個(gè)劃分.對(duì)任意i = 1，2，…，2n -1，令

其中下標(biāo)p + i -2 取模2n +1.

其次，用2n - 1 種色b0，b1，…，b2n-2染完全圖的邊，由引理3，使其成為的2n -1 - 鄰強(qiáng)邊染色，其中j = 1，2，…，2n + 1. 具體地，設(shè)的2n -1 個(gè)最大匹配為

其中下標(biāo)t + s 與t - s 取模2n -1.

其中下標(biāo)t + j -2 取模2n -1.

容易驗(yàn)證，f'為K2n-1×K2n+1'的4n -正常全染色，且有

其中下標(biāo)i + j -2 取模2n -1.

第三步，觀(guān)察矩陣ˉC'，每一列的任意兩元素均不相同.而每一行的前2n - 1 個(gè)元素互不相同，但第1 列和第2n 列，第2 列和第2n +1 列元素完全相同，故下面對(duì)頂點(diǎn)vi，2n和vi，2n+1(i = 1，2，…，2n -1)進(jìn)行改染.

其余頂點(diǎn)和邊的染法不變，即令

其中i ≠t，i，t = 1，2，…，2n -1;j ≠s，j，s = 1，2，…，2n -1.

下說(shuō)明f 是K2n-1×K2n+1'的鄰點(diǎn)可區(qū)別全染色.

若用矩陣ˉC 表示在染法f 下各頂點(diǎn)色集的缺色情況，則有

因此，f 是K2n-1× K2n+1' 的4n - AVDTC.

對(duì)于任意奇數(shù)階完全圖的直積圖K2s+1×K2t+1，若2s +1 與2t +1 不相鄰，如使用上述定理1 中的染色方法，不能構(gòu)成K2s+1×K2t+1的鄰點(diǎn)可區(qū)別全染色.因此對(duì)于任意奇數(shù)階完全圖的直積圖K2s+1×K2t+1的鄰點(diǎn)可區(qū)別全染色還需要做進(jìn)一步的討論.

［1］ ZHANG Zhong-fu，CHEN Xiang -en，etc. On Adjacent -Vertex-Distinguishing Total Coloring of Graphs［J］.Science in China Ser.A Mathematics，2005，48(3):289 -299.

［2］ Bondy J. A. and Murty U.S.R［M］.Graph Theory with Applications，Macmillan［M］. New York:Longdon and Elsevier，1976.

［3］ ZHANG Zhong - fu. Adjacent Strong Edge Coloring of Graphs［J］.Applied Mathematices letters，15(2002):623 -626.

［4］ 張琛，張如清，呂衛(wèi)東. K2s×K2t的鄰點(diǎn)可區(qū)別全染色［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42(20):213 -216.

［5］ 陳祥恩，張琛.直積圖的鄰點(diǎn)可區(qū)別全染色［J］. 蘭州理工大學(xué)學(xué)報(bào)，2008，34(2)，137 -140.

［6］ 張琛，陳祥恩，劉信生. 多重Mycielski 圖的鄰點(diǎn)可區(qū)別全染色［J］.西北師范大學(xué)學(xué)報(bào)，2007，43(6):22 -26.