路和圈冪圖的鄰點(diǎn)可區(qū)別E-全染色

董秀芳

(江蘇省聯(lián)合職業(yè)技術(shù)學(xué)院連云港財(cái)經(jīng)分院 數(shù)學(xué)與應(yīng)用數(shù)學(xué)系，江蘇 連云港222003)

1 基本概念與引理

假定所討論的圖G(V，E)都是有限、無向簡單連通圖. 設(shè)Δ(G)和δ(G)分別表示圖G 的最大度和最小度，T(G)是圖的頂點(diǎn)和邊組成集合. 令dG(u，v)表示G 中u，v2 個(gè)頂點(diǎn)最短路徑的長度，若期間沒有路徑，令其為dG(u，v)∶=∞，明確圖類的情況下，簡記為d(u，v).令［k］={1，2，…，k}為k-色集(k 是正整數(shù))，C(u)=表示頂點(diǎn)u 及其所有鄰邊的染色集合. 其他相關(guān)概念和術(shù)語請(qǐng)參看文獻(xiàn)［1］.

圖染色問題是圖論中的一個(gè)重要研究方向，為了解決計(jì)算機(jī)科學(xué)、信號(hào)處理等領(lǐng)域中遇到的問題，許多圖論專家相繼提出了圖的染色概念，如點(diǎn)可區(qū)別的邊染色［2－3］，鄰點(diǎn)可區(qū)別的邊染色［4－5］，點(diǎn)可區(qū)別的全染色［6］，鄰點(diǎn)可區(qū)別的全染色［7］等;2008 年張忠輔［8］等人又提出了圖的鄰點(diǎn)可區(qū)別E-全染色的概念，李沐春、王治文、王繼順［9－12］等研究了一些圖的鄰點(diǎn)可區(qū)別E-全染色. 確定圖的鄰點(diǎn)可區(qū)別E-全色數(shù)同樣是NP-難問題.

定義1［8］對(duì)簡單連通圖G(V，E)和正整數(shù)k，f 是T(G)到［k］={1，2，…，k}的一個(gè)映射，如果f 滿足

則稱f 為一個(gè)圖G 的鄰點(diǎn)可區(qū)別E-全染色，簡記為G 的k-AVDETC，并稱

為G 的鄰點(diǎn)可區(qū)別E-全色數(shù).

猜想1［8］對(duì)簡單圖G(Δ(G)≥4)，且G≠Kn，G≠C2n+1，則

定義2［13］對(duì)圖G(V，E)，若V(Gk)=V(G)，E(Gk)=E(G)∪{uv|d(u，v)=k}，稱Gk為圖G 的k-冪圖. 如路的2-冪圖P26，如圖1 所示.

馬生全，李敬文［13］等研究了Pkn(k≡2(mod 3))的鄰點(diǎn)可區(qū)別的強(qiáng)全染色，王繼順［14］獲得了Pkn(k≡2(mod 3))的D(2)-點(diǎn)可區(qū)別全色數(shù)，谷玉盈，王淑棟［15］確立了一些冪圖的鄰點(diǎn)可區(qū)別全色數(shù).筆者研究了的鄰點(diǎn)可區(qū)別E-全染色，通過給出其鄰點(diǎn)可區(qū)別E-全色數(shù)說明猜想1 對(duì)于這類圖是正確的.

圖1 路P6 及其2-冪圖（記作

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

引理1［1－2］對(duì)任意的簡單圖G，有χ(G)≤Δ(G)+1，等號(hào)成立當(dāng)且僅當(dāng)G 為奇圈或完全圖.

引理2［8］對(duì)任意的簡單圖G，有χ(G)≤χeat(G)≤χ(G)+1.

引理3［8］對(duì)任意的簡單圖G 和H，有

其中，G∨H 為G 和H 的聯(lián)圖.

引理4［8］設(shè)Cn為n 階圈，則

引理5［18］設(shè)Kn為n 階完全圖(n≥4)，則χeat(Kn)=n.

引理6 假定G 由m 個(gè)分支G1，G2，…，Gm組成，則有

證明 由定義1 易證結(jié)論成立.

定理1 設(shè)Pn是n(n≥2)階路，則

證明 假定Pn=v1v2v3…vn，由于P2n包含子圖K3，按照引理5 和引理6，有為證明結(jié)論成立，僅需證明P2n存在一個(gè)4-AVDETC.下面構(gòu)造T(P2n)到［4］的染色法f 如下

按照該染色法f，易得當(dāng)i≡1(mod 3)時(shí)，C(vi)={1，4}，當(dāng)i≡2(mod 3)時(shí)，C(vi)={2，4}，當(dāng)i≡0(mod 3)時(shí)，C(vi)={3，4}.

對(duì)任意相鄰的頂點(diǎn)u，v P2n，由于C(u)≠C(v)，所以f 是P2n的一個(gè)4-AVDETC.

定理2 對(duì)n(n≥2)階路Pn的k-冪圖Pkn(n≥2k+2，k≥2)，有

證明 假定Pn=v1v2v3…vn，由于包含子圖Ck+1，按照引理4 和引理6，當(dāng)k 是奇數(shù)時(shí)當(dāng)k 是偶數(shù)時(shí)為證明結(jié)論成立，僅需證明當(dāng)k≡1(mod 2)時(shí)，Pkn存在一個(gè)3-AVDETC，當(dāng)k≡0(mod 2)時(shí)，Pkn 存在一個(gè)4-AVDETC. 為此分2 種情況討論如下

情形1 當(dāng)k≡1(mod 2)時(shí)，構(gòu)造T(Pkn)到［3］的染色法f 如下

下面驗(yàn)證該染色法f 滿足定義1

易見f 是Pkn(k≡1(mod 2))的一個(gè)3-AVDETC. 事實(shí)上，一方面對(duì)任意相鄰頂點(diǎn)vi，vi+1，，有C(vi)≠C(vi+1);另一方面，對(duì)任意頂點(diǎn)vi，由于i 和i+k 總是奇偶性相反，所以C(vi)≠C(vi+k). 從而(k≡1(mod 2)).

情形2 當(dāng)k≡0(mod 2)時(shí)，按照如下的2 種情況定義從T(Pkn)到［4］的一個(gè)全染色法f

1)當(dāng)k≡0(mod 2)，且k≠0，2(mod 10)時(shí)，令f

下面驗(yàn)證上述的染色法f 滿足定義1

當(dāng)k≠0，2(mod 10)時(shí)，由于k 是偶數(shù)，i +k 與i 的模不會(huì)相同，所以C(vi)≠C(vi+k)且C(vi)≠C(vi+1).故f 是Pkn的一個(gè)4-AVDETC，結(jié)論成立.

2)當(dāng)k≡0(mod 2)，且k≡0，2(mod 10)時(shí)，構(gòu)造f

對(duì)此染色法f，易得

所以，f 是Pkn(k≡0(mod 2))的一個(gè)4-AVDETC，結(jié)論成立.

定理3 令Cn為n(n≥3)階圈，則有

證明 令Cn=v1v2v3…vnv1.下面分3 種情況討論.

易見f 是C2n的一個(gè)4-AVDETC. 事實(shí)上，C2n所有相鄰的頂點(diǎn)染色集是不同的，當(dāng)i≡1(mod 3)時(shí)，C(vi)={1，4}，當(dāng)i≡2(mod 3)時(shí)，C(vi)={2，4}，當(dāng)i≡0(mod 3)時(shí)，C(vi)={3，4}.所以(n≡0(mod 2)).

情形2 當(dāng)n≡1(mod 3)時(shí)，因?yàn)镃2n包含子圖K3，所以按照引理5 和引理現(xiàn)只要構(gòu)造C2n的一個(gè)4-AVDETC 染色法f

則有

易見f 是C2n(n≡1(mod 2))的一個(gè)4-AVDETC . 故而結(jié)論成立.

情形3 當(dāng)n≡2(mod 3)時(shí)，由于C2n包含子圖K3，則由引理5 和引理6 有運(yùn)用反證法說明C2n的4-不可染. 若用4 種顏色可得C2n的一個(gè)4-AVDETC，不妨先從i=1 用色1，2，3 分別染K3的頂點(diǎn)(vi，vi+1，vi+2)，依次循環(huán)染到第(n－2)/3 個(gè)K3. 至此還有vn－1，vn沒有染. 現(xiàn)已不能用色1，2，3 染頂點(diǎn)vn－1，因?yàn)槠湎噜忢旤c(diǎn)v1，vn－2，vn－3已經(jīng)分別用過1，2，3(如圖2 所示). 所以只能用色4 染vn－1.再看vn，因?yàn)関n與頂點(diǎn)v1，v2，vn－2，vn－1都相鄰，已經(jīng)分別用1，2，3，4 分別染色，所以從1 到4 的4 種色不能滿足得到一個(gè)4-AVDETC 的條件(如圖3 所示)，否則與定義1 矛盾. 故只能用第五種色來染vn不妨令其為5. 由上述的討論，C2n需要5 色才能滿足5-AVDETC 的條件，下面給出C2n的一個(gè)5-AVDETC.

圖2 vn-1 的鄰點(diǎn)

圖3 vn 的鄰點(diǎn)

該染色法f 滿足定義1

顯然，f 是C2n的一個(gè)5-AVDETC. 從而結(jié)論成立.

［1］BONDY J A，MURTY U S R. Graph Theory［M］.New York:Springer，2008.

［2］BURRIS A C，SCHELP R H. Vertex-distinguishing proper edge-colorings［J］. Graph Theory，1997，26(2):73 －82.

［3］BAZGAN C，HARKAT-BENHAMDINE A，LI Hao，et al. On the vertex-distinguishing proper edge-colorings of graphs［J］. J.Combin. Theory Ser. B，1999，75(2):288 －301.

［4］ZHANG Zhongfu，LIU Linzhong，WANG Jianfang. Adjacent strong edge coloring of graph［J］.Applied Mathematics Letters，2002，15(5):623 －626.

［5］張忠輔，李敬文，陳祥恩，等.圖的距離不大于β 的任意兩點(diǎn)可區(qū)別邊染色［J］. 數(shù)學(xué)學(xué)報(bào)，2006，49(3):703 －708.

［6］ZHANG Zhongfu，QIU Pengxiang，XU Baogen，et al. Vertex-distinguishing total coloring of graphs［J］. ArsCombinatoria，2008，87:33 －45.

［7］ZHANG Zhongfu，CHEN Xiangen，LI Jing-wen，et al. On adjacent-vertex-distinguishing total coloring of graphs［J］. Science ChinaSeries A:Mathematics，2005，48(3):289 －299.

［8］ZHANG Zhongfu，DOUGLAS R W，YAO Bing，et al. Edge adjacent vertex-distinguishing total coloring of graphs［EB/OL］.(2008 －06 －12)［2014 －02 －10］.http://202.201.18.40:8080/mas5/.

［9］李沐春，張忠輔.若干笛卡爾積圖的鄰點(diǎn)可區(qū)別E-全染色［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2009，39(3):215 －219.

［10］周登杰，李沐春. 路和圈多重聯(lián)圖的鄰點(diǎn)可區(qū)別E-全染色［J］. 純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2010，26(6):909 －914.

［11］王治文，張威，李沐春，等. 圈的多重聯(lián)圖的鄰點(diǎn)可區(qū)別E-全染色的一些結(jié)果［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2010，40(20):177 －180.

［12］WANG Jishun. Adjacent vertex-distinguishing E-total coloring on some join graphs Cm∨Gn［J］.Chinese Quarterly Journal of Mathematics，2012，27(3):328 －336.

［13］馬生全，李敬文，馬明，等.Pkn(k≡2(mod 3))的鄰點(diǎn)可區(qū)別的強(qiáng)全染色［J］. 經(jīng)濟(jì)數(shù)學(xué)，2003(4):77 －80.

［14］王繼順.Pkn(k≡2(mod 3))的D(2)-點(diǎn)可區(qū)別全染色［J］. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2011，41(2):190 －194.

［15］谷玉盈，王淑棟.冪圖的鄰點(diǎn)可區(qū)別全色數(shù)［J］.黑龍江大學(xué)學(xué)報(bào):自然科學(xué)版，2008，25(2):193 －195.