特殊圖的廣義字典積的鄰點(diǎn)可區(qū)別全染色

趙曉翠，田雙亮，何雪，焉秋瑤

（西北民族大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，甘肅蘭州730030）

特殊圖的廣義字典積的鄰點(diǎn)可區(qū)別全染色

趙曉翠，田雙亮，何雪，焉秋瑤

（西北民族大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，甘肅蘭州730030）

設(shè)G是具有頂點(diǎn)集V（G）＝{t0，…，tn-1}（n≥2）的圖，hn=（Hi）i∈{0,1，…，n-1}是不相交圖的序列，其中Hi的頂點(diǎn)集為V（Hi）={（ti，y1)，…，（ti，yx)}，x≥1。稱G[hn]為G與hn=（Hi）i∈{0,1，…，n-1}的廣義字典積，其中G[hn]的頂點(diǎn)集為，且兩個頂點(diǎn)（ti，yp)與（tj，yq)相鄰當(dāng)且僅當(dāng)ti=tj且（ti，yp)（ti，yq)∈E（Hi），或（ti，tj）∈E（G）。研究了一些廣義字典積G[hn]的鄰點(diǎn)可區(qū)別全染色，其中G表示n≥6階輪，扇或星。

廣義字典積；鄰點(diǎn)可區(qū)別全染色；鄰點(diǎn)可區(qū)別全色數(shù)

1 知識準(zhǔn)備

筆者所考慮的圖G都是有限無向的簡單圖，用V（G），E（G）分別表示G的點(diǎn)和邊的集合。并用Δ（G）與D（G）分別表示G的最大度與直徑。

定義1[1]設(shè)G是具有頂點(diǎn)集V（G）＝{t1，t2，…，tn}，n≥2的圖，hn=（Hi）i∈{1，2，…，n}是不相交圖的序列，其中圖Hi的頂點(diǎn)集V（Hi）={（ti，y1)，（ti，y2)，…，（ti，yx)}，x≥1。稱G[hn]為G與hn=（Hi）i∈{1，2，…，n}的廣義字典積，其中G[hn]的頂點(diǎn)集為，且兩個頂點(diǎn)（ti，yp)與（tj，yq)相鄰當(dāng)且僅當(dāng)ti=tj且（ti，yp)（ti，yq)∈E（Hi），或titj∈ E（G），若Hi≌H，則G[hn]記為G[H]，且稱G[H]為G與H的字典積。

由定義1，兩個圖G1與G2的聯(lián)圖[2]G1∨G2可看成P2[h2]，其中h2=（Gi）i∈{1，2}。G與hn=（Hi）i∈{1，2，…，n}的廣義字典積G[hn]也可稱為不相交圖H1，H2，…，Hn關(guān)于G的廣義聯(lián)圖[3]。等廣義聯(lián)圖G（n，H）為n階圖G與H的字典積G[H]。完全多部圖可看成是完全圖與若干零圖（完全圖的補(bǔ)圖）序列的廣義字典積，如每部分有m個頂點(diǎn)的等完全n-部圖K（n，m）是n階完全圖Kn與m階完全圖的補(bǔ)圖Km的字典積圖。多重聯(lián)圖[4]K（G1，G2，…，Gn）則可看成是n階完全圖Kn與hn=（Gi）i∈{1，2，…，n}的廣義字典積。

定義2[5]設(shè)G是階至少為2的連通圖，k是正整數(shù)且σ是一從V（G）∪E（G）到{1,2，…，k}的映射。對任意u∈V（G），用C（u）表示{σ（u）}∪{σ（uv）|uv∈E（G）}。如果：

（1）對任意uv，vw∈E（G），u≠w，有σ（uv）≠σ（vw）；

（2）對任意uv∈E（G），有σ（u）≠σ（v），σ（u）≠σ（uv），σ（v）≠σ（uv），則稱σ是G的k-正常全染色。若σ是G的k-正常全染色，且

（3）對任意uv∈E（G），有C（u）≠C（v），則稱σ是G的一k-鄰點(diǎn)可區(qū)別全染色（簡記為k-AVDTC）。且稱χat（G）=min{k|G存在k-AVDTC}為G的鄰點(diǎn)可區(qū)別全色數(shù)。

定義2中C(u)稱為點(diǎn)u在σ下的色集合,C(u)在全體顏色構(gòu)成的集合C={1,2,…，k}中的補(bǔ)集記為。

對階至少為2的簡單連通圖G，χat（G）顯然存在。

由定義2，容易得到以下引理：

引理1如果圖G有兩個相鄰的最大度點(diǎn)，則χat（G）≥Δ（G）+2，其中Δ（G）為G的最大度。

Burris與Schelp在文獻(xiàn)[6]中提出了關(guān)于圖的點(diǎn)可區(qū)別邊染色猜想：對沒有孤立邊且至多含有一個孤立頂點(diǎn)的n階圖G，有χ′vd（G）≤n+1，其中χ′vd（G）表示G的點(diǎn)可區(qū)別邊色數(shù)。Cristina Bazgan等在文獻(xiàn)[7]中證明了該猜想正確。由此結(jié)果可知，n≥3階簡單連通圖G與平凡圖K1（僅含一個頂點(diǎn)的圖）的聯(lián)圖的點(diǎn)可區(qū)別邊色數(shù)不超過n+2，將G的每一頂點(diǎn)染成該頂點(diǎn)與K1的頂點(diǎn)連邊所染顏色，并刪去K1的頂點(diǎn)，則可得到G的一個（n+2）-鄰點(diǎn)可區(qū)別全染色。因此，有以下引理：

引理2對n≥3階簡單連通圖G，有χat（G）≤n+2。

在以后的討論中要用到以下引理：

引理3[8]對n階完全圖Kn，有。其中χT（Kn）為Kn的全色數(shù)。

引理4[5]對n階完全圖Kn，n≥2，有。

引理5[5]對n階完全圖Cn，n≥4，有χat（Cn）=4。

文獻(xiàn)[5]給出了圈、完全圖、完全二部圖、扇、輪和樹的鄰點(diǎn)可區(qū)別全色數(shù)。文獻(xiàn)[9]給出了圈與扇的聯(lián)圖，得到了在不同取值情況下的鄰點(diǎn)可區(qū)別全色數(shù)。文獻(xiàn)[10]給出了幾類特殊圖的鄰點(diǎn)可區(qū)別全色數(shù)。文獻(xiàn)[11]得到了兩條路的聯(lián)圖的鄰點(diǎn)可區(qū)別全色數(shù)。筆者將研究廣義字典積G[hn]中G為n階輪，扇或星時的鄰點(diǎn)可區(qū)別全染色。文中未加說明的術(shù)語及符號可參見文獻(xiàn)[2]和文獻(xiàn)[8]。

2 主要結(jié)果

下面研究當(dāng)G為n階輪，扇或星時，G與hn=（Hi）i∈{0,1，…，n-1}的廣義字典積G[hn]的鄰點(diǎn)可區(qū)別全染色，其中Hi為m階簡單圖，i=0,1,…,n-1且n≥6，m≥3。

設(shè)n階輪Wn的頂點(diǎn)集和邊集分別為V（Wn）＝{t0，t1，…，tn-1}，E（Wn）＝{tn-1tj|j=0,1,…,n-2}∪{t0t1，t1t2，…，tn-3tn-2，tn-2t0}。n階扇Fn與星Sn分別可由輪Wn刪去一些邊得到。為敘述方便，令V（Hi）={（ti，yj)|j=1,2,…,m}，并記vij=（ti，yj)。在G[hn]中，用Gkl表示具有二分類（V（Hk），V（Hl）)的m-正則二部圖。

若G是n階的輪即G=Wn，由圖的廣義字典積的定義，可將圖G[hn]分解為三個邊不交子圖G（1），G（2）與G（3），即其中，G（3）=G01∪G12∪…∪Gn-3，n-2∪Gn-2，0。

定理1若Hn-1為空圖，則χat（G[hn]）=（n-1）m+1。

證明假設(shè)G=Wn。情形G=Fn與G=Sn的證明過程類似。記G*=G[hn]。因χat（G*）≥Δ（G*）+1=（n-1）m+1。欲證χat（G*）≤（n-1）m+1，僅需給出G*的一個（（n-1）m+1）-AVDTC。

首先，對G（2）進(jìn)行邊染色。用Ai中的m種顏色對m-正則二部圖Gn-1，i進(jìn)行正常邊染色，i=1,2,…,n-1。

其次，對G（3）進(jìn)行邊染色。用Ai+3（下標(biāo)i+3取模n-1）中的m種顏色對m-正則二部圖Gij進(jìn)行正常邊染色，i=0,1,…,n-2。

最后，對G（1）進(jìn)行鄰點(diǎn)可區(qū)別全染色。具體地，用An-1中的一種顏色對Hn-1的頂點(diǎn)進(jìn)行染色；由引理2，用Ai+1∪{ai+4，0，ai+4，1}（下標(biāo)i+1與i+4均取模n-1）中的m+2種顏色對Hi進(jìn)行鄰點(diǎn)可區(qū)別全染色，使得Hi的頂點(diǎn)不染顏色ai+4，0與ai+4，1，i=0,1,…,n-2。

顯然，以上染色σ是G[hn]的一個（（n-1）m+1）-正常全染色，且Hi中的任意相鄰頂點(diǎn)在σ下有不同的色集合，其中i=0,1,…,n-1。因當(dāng)n≥6時，對i=0,1,…,n-2，Hn-1的頂點(diǎn)與Hi的頂點(diǎn)的度數(shù)不相等，所以它們在σ下有不同的色集。因Hi的每一頂點(diǎn)在σ下的色集合必包含Ai∪Ai+2∪Ai+3，但對任意i≠j，Hj的每一頂點(diǎn)在σ下的色集合至少不含Ai∪Ai+2∪Ai+3中的一種顏色，i，j=0,1,…,n-2，因此，所構(gòu)造染色σ是G[hn]的一個（（n-1）m+1）-鄰點(diǎn)可區(qū)別全染色，即χat（G[hn]）≤（n-1）m+1。故定理結(jié)論成立。

定理2若Hn-1為完全圖，則χat（G[hn]）=nm+1。

證明假設(shè)G=Wn。情形G=Fn與G=Sn的證明過程類似。記G*=G[hn]。因G*的最大度為nm-1且最大度點(diǎn)相鄰，由引理1，χat（G*）≥Δ（G*）+2=nm+1。欲證χat（G*）≤nm+1，僅需給出G*的一個（nm+1）-AVDTC。

情況1m是奇數(shù)。由（1）式知，可分三步對G*進(jìn)行全染色。

首先，對G（2）進(jìn)行邊染色。用Ai中的m種顏色對m-正則二部圖Gn-1，i進(jìn)行正常邊染色，i=1,2,…,n-2；用A0∪An中的m+1種顏色對Gn-1，0進(jìn)行如下邊染色：當(dāng)i+j≠m+1時，令f（vn-1，iv0j）=a0，i+j-1（mod n+1），i，j=0,1,…, m-1；當(dāng)i+j=m+1時，令f（vn-1，iv0j）=b，i，j=0,1,…,m-1。

其次，對G（3）進(jìn)行邊染色。用Ai+3（下標(biāo)i+3取模n-1）中的m種顏色對m-正則二部圖Gij進(jìn)行正常邊染色，i=0,1,…,n-2。

最后，對G（1）進(jìn)行鄰點(diǎn)可區(qū)別全染色。具體地，由引理3，用An-1中的m種顏色對Hn-1進(jìn)行正常全染色；由引理2，用Ai+1∪{an-1，0，an-1，1}（下標(biāo)i+1取模n-1）中的m+2種顏色對Hi進(jìn)行鄰點(diǎn)可區(qū)別全染色，使得Hi的頂點(diǎn)不染顏色an-1，0與an-1，1，i=0,1,…,n-2。

顯然，以上染色σ是G[hn]的一個（nm+1）-正常全染色，類似于定理1證明中的討論，所構(gòu)造染色σ是G[hn]的一個（nm+1）-鄰點(diǎn)可區(qū)別全染色，即χat（G[hn]）≤nm+1。故定理結(jié)論成立。

情況2m是偶數(shù)。與情況1類似，可分三步對G*進(jìn)行全染色。

首先，對G（2）進(jìn)行邊染色。用Ai中的m種顏色對m-正則二部圖Gn-1，i進(jìn)行正常邊染色，i=1,2,…,n-1。

其次，對G（3）進(jìn)行邊染色。用Ai+3（下標(biāo)i+3取模n-1）中的m種顏色對m-正則二部圖Gij進(jìn)行正常邊染色，i=0,1,…,n-2。

最后，對G（1）進(jìn)行鄰點(diǎn)可區(qū)別全染色。具體地，由引理4，用An-1∪An中的m+1種顏色對Hn-1進(jìn)行點(diǎn)可區(qū)別全染色；由引理2，用Ai+1∪{an-1，0，an-1，1}（下標(biāo)i+1取模n-1）中的m+2種顏色對Hi進(jìn)行鄰點(diǎn)可區(qū)別全染色，使得Hi的頂點(diǎn)不染顏色an-1，0與an-1，1，i=0,1,…,n-2。

顯然，以上染色σ是G[hn]的一個（nm+1）-正常全染色，類似于定理1證明中的討論，所構(gòu)造染色σ是G[hn]的一個（nm+1）-鄰點(diǎn)可區(qū)別全染色，即χat（G[hn]）≤nm+1。故定理結(jié)論成立。

定理3若Hn-1為圈，則χat（G[hn]）＝（n-1）m+4。

假設(shè)G=Wn。情形G=Fn與G=Sn的證明過程類似。記G*=G[hn]。因G*的最大度為（n-1）m+2且最大度點(diǎn)相鄰，由引理1，χat（G*）≥Δ（G*）+2=（n-1）m+4。欲證χat（G*）≤（n-1）m+4，僅需給出G*的一個（（n-1）m+4）-AVDTC。

顯然，以上染色σ是G[hn]的一個（（n-1）m+4）-正常全染色，類似于定理1證明中的討論，所構(gòu)造染色σ是G[hn]的一個（（n-1）m+4）-鄰點(diǎn)可區(qū)別全染色，即χat（G[hn]）≤（n-1）m+4。故定理結(jié)論成立。

定理4若Hn-1為輪，扇或星，則χat（G[hn]）＝nm。

證明設(shè)G=Wn。情形G=Fn與G=Sn的證明過程類似。記G*=G[hn]。因G*的最大度為nm-1，所以χat（G*）≥Δ（G*）+1=nm。欲證χat（G*）≤nm，僅需給出G*的一個（nm）-AVDTC。

顯然，以上染色σ是G[hn]的一個（nm）-正常全染色，類似于定理1證明中的討論，所構(gòu)造染色σ是G[hn]的一個（nm）-鄰點(diǎn)可區(qū)別全染色，即χat（G[hn]）≤nm。故定理結(jié)論成立。

[1]Waldemar Szumny，Iwona Wloch，Andrzej Wloch．On the existance and on the number of（k，l）-kernels in the lexicographic product of graphs[J]．Discrete Mathematics，2008，308：4616-4624．

[2]Bondy J A，Murty U S R．Graph Theory with Application[M]．New York：Macmillan Press Ltd，1976．

[3]Tian Shuangliang．Star total colorings of mycielski’s graphs of balanced general join of graph[J]．Journal of Shandong University（Natural Science），2009，45（6）：23-26，34．

[4]田雙亮，陳萍．若干多重聯(lián)圖的邊染色[J]．南開大學(xué)學(xué)報：自然科學(xué)版，2007，40（3）：27-30．

[5]張忠輔，陳祥恩，李敬文，等．關(guān)于圖的鄰點(diǎn)可區(qū)別全染色[J]．中國科學(xué)A輯，2004，34（5）：574-583．

[6]Burris A C，Schelp R H．Vertex-distinguishing proper edge colorings[J]．Journal of Graph Theory，1997，26：73-82．

[7]Bazgan C，Harkat-Benhamdine A，Hao Li，et al．On theVertex-distinguishing proper edge colorings of graphs[J]．Journal of Combinatorial Theory，1999，75：288-301．

[8]Yap H P．Total Colourings of Graphs[M]．New York：Springer-Verlag，1996．

[9]馬剛，張煒，張忠輔．圖Cm∨Fn的鄰點(diǎn)可區(qū)別全染色[J]．西北民族大學(xué)學(xué)報：自然科學(xué)版，2005，26（2）：24－29．

[10]董海燕，孫磊，孫艷麗．關(guān)于鄰點(diǎn)可區(qū)別全染色的幾個新結(jié)果[J]．廣西師范大學(xué)學(xué)報：自然科學(xué)版，2005，23（3）：41－43．

[11]陳祥恩，張忠輔．Pm∨Pn的鄰點(diǎn)可區(qū)別全染色[J]．西北師范大學(xué)學(xué)報：自然科學(xué)版，2005，41（1）：13－15．

Adjacent vertex distinguishing total coloring of the generalized lexicographic product of special graphs

ZHAO Xiaocui，TIAN Shuangliang，HE Xue，YAN Qiuyao
（School of Mathematics and Computer Science，Northwest University for Nationalities，Lanzhou 730030，China）

Let G be a graph on V（G）＝{t0，…，tn-1}（n≥2）and hn=（Hi）i∈{0,1，…，n-1}be a sequence of vertex disjoint graphs on V（Hi）={（ti，y1)，…，（ti，yx)}，x≥1．By the generalized lexicographic product of G and hn=（Hi）i∈{0,1，…，n-1}we mean the graph G[hn]such that，and two distinct vertices（ti，yp)and（tj，yq)are adjacent if and only if ti=tjand（ti，yp)（ti，yq)∈E（Hi），or（ti，tj）∈E（G）．In this paper，we have studied adjacent vertex distinguishing total coloring of the generalized lexicographic product G[hn]of special graphs，where G is an wheel，a fan or a star with n≥6 vertices．

generalized lexicographic product；adjacent vertex distinguishing total coloring；adjacent vertex distinguishing total chromatic number

O157.5MR（2000）Subject Classification：05C15

A

1672－0687（2015）01－0016－04

責(zé)任編輯：謝金春

2013－09－06

國家自然科學(xué)基金資助項(xiàng)目（11161041）；國家民委科研資助項(xiàng)目（10XB01）；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目（zyz2012089）；西北民族大學(xué)中央高校科研專項(xiàng)資金資助研究生項(xiàng)目（ycx13160）；西北民族大學(xué)中央高?？蒲袑ｍ?xiàng)資金資助研究生項(xiàng)目（ycx13163）

趙曉翠（1989-），女，陜西韓城人，碩士研究生，研究方向：圖論及組合優(yōu)化。