蛛形圖的全圖和中心圖的均勻染色＊

趙金麗， 卜月華

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

用V(G)和E(G)分別表示圖G的頂點集和邊集．稱映射φ:V(G)→{1，2，…，k}為圖G的一個正常k-染色，如果φ使得V(G)中任何2個相鄰的頂點u，v，φ(u)≠φ(v);稱χ(G)為最小的顏色數(shù)k，使得圖G 有正常 k-染色［1］．如果 G 的頂點集合可以剖分成 k 個獨立集 V1，V2，…，Vk，使得||Vi|-|Vj||≤1(i≠j)成立，則稱圖G是k-均勻可染的，(V1，V2，…，Vk)稱為一個均勻獨立集剖分．使得圖G均勻k-可染的最小的整數(shù) k 為圖 G 的均勻色數(shù)，記為 χEq(G)［2］．顯然，χEq(G)≥χ(G)．

給定一個圖G=(V，E)，對圖G每一條邊分割1次，即在每條邊上插入一個頂點，連接所有在G中不相鄰的頂點．對圖G進行這樣的操作后所得到的圖稱為G的中心圖，記為C(G)．

給定一個圖G，定義圖G的全圖T(G)如下:T(G)的頂點集合為V(G)∪E(G)，T(G)中滿足下面條件之一的2個頂點x，y相鄰:

1)x，y∈V(G)以及 x，y在 G 中相鄰;

2)x，y∈E(G)以及 x，y在 G 中相鄰;

3)x∈V(G)，y∈E(G)，x，y在 G 中關(guān)聯(lián)．

一個圖G稱為是一個蛛形圖［3］，若G是一棵樹且至多存在一個度數(shù)大于2的頂點v，頂點v稱為頭點．蛛形圖有時也稱為廣義星圖．

對于一些特殊圖的全圖和中心圖的均勻染色，Ali Akbar等［4］撰文進行了討論，得到了如下結(jié)果:

定理1［4］路Pn的全圖的均勻色數(shù) χEq［T(Pn)］=3．

定理 2［4］對于圈 Cn，若 n≡0(mod 3)，則 χEq［T(Cn)］=3．

而當(dāng)n不能被3整除時，其均勻色數(shù)的情況仍不清楚．

定理 3［4］星圖 K1，n的中心圖的均勻色數(shù) χEq［C(K1，n)］=n．

定理 4［4］等完全二部圖 Kn，n(n≥3)的中心圖的均勻色數(shù) χEq［C(Kn，n)］=n．

定理5［4］完全圖Kn(n≥4)的中心圖的均勻色數(shù) χEq［C(Kn)］=3．

有關(guān)均勻染色的其他結(jié)果可參考文獻［5］．

本文討論了蛛形圖的全圖和中心圖的均勻染色問題，得到了蛛形圖的全圖的均勻色數(shù)(定理6)和蛛形圖的中心圖的均勻色數(shù)(定理7)．

定理6 設(shè)G是一個蛛形圖，刪去頭點后共有n(n≥3)條路，該n條路記為Pi(1≤i≤n)，且|Pi|=n-1，則 χEq［T(G)］=n+1．

證明 設(shè)蛛形圖G的頭點為v，刪去v后，把該n條路分別記為Pi=vi1vi2…vin(1≤i≤n)，eij表示Pi中連接 vi(j-1)和 vij(1≤i≤n，2≤j≤n)的邊，連接 v 與 vi1的邊記為 ei1(1≤i≤n)．NT(G)(vij)表示點 vij在T(G)中的鄰域．

根據(jù)全圖的定義，有:

因 T(G)是包含由 v，e11，e21，…，en1的 n+1 個頂點所構(gòu)成的完全子圖，故 χEq［T(G)］≥χ［T(G)］≥n+1．另一方面，若能夠證明頂點集合V［T(G)］可以劃分成n+1個獨立集，且任意2個獨立集之間的元素個數(shù)至多相差1，則有 χEq(［T(G)］)≤n+1．

為了證明方便，分n≤6和n≥7兩種情況來證明．當(dāng)n≤6時，具體給出每個獨立集的元素，從而證明 χEq(［T(G)］)=n+1．

1)n≤6．

①n=3．令:T1={e11，v21，v23，v31，v33};T2={e21，v13，e12，e32，v22};T3={v11，e13，e22，v32，e31};T4={v，v12，e23，e33}．Ti(i=1，2，3，4)是元素個數(shù)分別為 5，5，5，4 的獨立集，此獨立集剖分滿足條件“任意獨立集之間的元素個數(shù)至多相差1”．

②n=4．令:T1={v13，e11，v21，v31，e33，v41};T2={v23，e21，e14，e34，v42，e44};T3={v33，e31，e12，v24，e22，v44，e42};T4={v11，e13，v22，e24，e32，v43，e41};T5={v，v12，e23，v32，e43，v14，v34}．Ti(i=1，2，3，4，5)是元素個數(shù)分別為6，6，7，7，7的獨立集，此獨立集剖分滿足條件“任意獨立集之間的元素個數(shù)至多相差1”．

③n=5．令:T1={e11，v21，v31，e33，v41，v51，e53，v44};T2={v24，e21，e14，e34，v42，e44，v52，e54};T3={e31，v13，e15，v23，v43，v53，e55，v11};T4={e41，v15，e12，v25，e22，v35，e32，v55，e52};T5={v54，e51，e13，v22，e24，v33，e35，v45，e42};T6={v，v14，e23，e43，v12，v32，v34，e25，e45}．Ti(i=1，2，3，4，5，6)是元素個數(shù)分別為 8，8，8，9，9，9 的獨立集，此獨立集剖分滿足條件“任意獨立集之間的元素個數(shù)至多相差1”．

④n=6．同理成立(略)．

2)n≥7．令:Vij={vij，ei(j+2)}，1≤j≤n-2;Vi(n-1)={vi(n-1)，ei1};Vin={vin，ei2}．其中 1≤i≤n．每個Vij(1≤i，j≤n)的元素個數(shù)都為2，共有n2個集合，每個集合在T(G)中都是獨立集，現(xiàn)在用這些集合繼續(xù)構(gòu)造n個獨立集．令:

至此，上述n2個集合Vij(1≤i，j≤n)合并為n個獨立集，每個獨立集的元素個數(shù)均為2n，則還剩下頭點v沒包括進去，從T1到Tn-1中分別選取2個不與頭點v相鄰的、且彼此也都不相鄰的頂點，共同構(gòu)成Tn+1．此時分2種情況:

①n為奇數(shù)．在每個Ti(1≤i≤n-2)中選取2個頂點，取法如下:

當(dāng)i是奇數(shù)時，在Ti中選取頂點e2(i+2)，e(n-1)(i+2);當(dāng)i是偶數(shù)時，在 Ti中選取頂點v1i，v(n-2)i．然后再在Tn-1中選取頂點v1n，v(n-2)n．所選取的2(n-1)個頂點互不相鄰．令:

②n為偶數(shù)．在每個Ti(1≤i≤n-2)中選取2個頂點，取法如下:

當(dāng)i是奇數(shù)時，在Ti中選取頂點e2(i+2)，e(n-1)(i+2);當(dāng)i是偶數(shù)時，在Ti中選取頂點v1i，v(n-2)i．然后再在Tn-1中選取頂點e32，e42．所選取的2(n-1)個頂點互不相鄰．令:

定理7 設(shè)G是一個蛛形圖，刪去頭點后共有n(n≥3)條路，該n條路記為Pi(1≤i≤n)，且|Pi|=

證明 記v為蛛形圖G的頭點，刪去v后，把該n條路分別記為Pi=vi1vi2… vin，1≤i≤n，在C(G)中，vi(j-1)與 vij之間插入的頂點記為 uij(1≤i≤n，1≤j≤n)．其中:vi0=v;NC(G)(vij)表示點 vij在 C(G)中的鄰域．根據(jù)中心圖的定義，有:

因為原圖中不相鄰的頂點在中心圖C(G)中相鄰，所以C(G)中的每個獨立集至多含V(G)中的2個頂點，且只能是在G中相鄰的2個頂點．下面根據(jù)n的不同情況進行討論．

此時，有|Vi1|=3(2≤i≤n)，|Vi((n+1)/2)|=3(1≤i≤n)，|V11|=4，|Vij|=4(1≤i≤n，2≤j≤(n-1)/2)滿足均勻染色的條件，所以當(dāng)n=2k+1時，χEq［C(G)］=(k+1)n=(k+1)×(2k+1)=2k2+3k+1．定理7證畢．

關(guān)于確定圖的全圖和中心圖的均勻色數(shù)的文獻還非常少，可以繼續(xù)研究的問題依然很多，如:

問題1 在定理6和定理7中的蛛形圖刪去頭點后路長為l(l≠n-1)的情況下，其全圖和中心圖的均勻色數(shù)為多少?

問題2 其他結(jié)構(gòu)稍復(fù)雜的圖類，如二叉樹等，其全圖和中心圖的均勻色數(shù)為多少?

［1］卜月華．圖論及其應(yīng)用［M］．南京:東南大學(xué)出版社，2000:198-199．

［2］Zhu Junlei，Bu Yuehua．Equitable list coloring of planar graphs without short cycles［J］．Theoretical Comput Sci，2008，407(1/2/3):21-28．

［3］Marek Kubale．Graph Colorings［M］．Rhode Island:American Mathematical Society，2004:139-144．

［4］Ali Akbara M M，Kaliraja K，Vernold Vivinb J．On Equitable Coloring of Central Graphs and Total Graphs［J］．Electronic Notes in Discrete Mathematics，2009，33(1):1-6．

［5］朱俊蕾，卜月華．圖 Pn∨Km，n的均勻全色數(shù)［J］．浙江師范大學(xué)學(xué)報:自然科學(xué)版，2007，30(1):58-64．