復(fù)合交叉圈的鄰點(diǎn)可區(qū)別全色數(shù)

楊 超, 姚 兵, 王宏宇

(西北師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 蘭州 730070)

1 引言及概念

圖的染色和標(biāo)號(hào)是當(dāng)今圖論學(xué)科中十分活躍的分支,它們?cè)诰幋a理論、通訊網(wǎng)絡(luò)、物流等方面均有應(yīng)用[1-4].圖的鄰點(diǎn)可區(qū)別全染色的概念第一次被張忠輔等[5]提出,并提出了以下的鄰點(diǎn)可區(qū)別全染色猜想:

猜想1[5]對(duì)于階數(shù)不小于 2的簡(jiǎn)單連通圖G,有

然而, 諸多文獻(xiàn)的結(jié)論表明, 解決上述猜想較困難. 近些年來(lái),對(duì)此猜想的研究成果不斷報(bào)道[6-10],Wang等[7]對(duì)平面圖驗(yàn)證了鄰點(diǎn)可區(qū)別全染色猜想, 取得了較好的結(jié)論. 令平面圖G的最小圈長(zhǎng)為g(G), 他們證明了: 當(dāng)g(G)≥6和Δ(G)=4時(shí),當(dāng)g(G)≥8和Δ(G)=3時(shí),5. 然而,對(duì)于最小圈長(zhǎng)g(G)≤5的平面圖的鄰點(diǎn)可區(qū)別全染色還有待研究, 沒(méi)有一般的方法來(lái)確定他們的鄰點(diǎn)可區(qū)別全色數(shù).

本文研究一類復(fù)合交叉圈,驗(yàn)證了鄰點(diǎn)可區(qū)別全染色猜想,得到了它在最小圈長(zhǎng)不超過(guò)5時(shí)的鄰點(diǎn)可區(qū)別全色數(shù),從而促進(jìn)了對(duì)最小圈長(zhǎng)不超過(guò)5的平面圖的鄰點(diǎn)可區(qū)別全染色問(wèn)題的研究. 文中論及的圖均為有限、無(wú)向簡(jiǎn)單圖, 且采用標(biāo)準(zhǔn)的圖論術(shù)語(yǔ)和符號(hào),可參見(jiàn)文獻(xiàn)[11].

引理1[5]設(shè)Pn是n階路. 當(dāng)n≥4時(shí),當(dāng)n=2,3時(shí),

引理2[5]設(shè)Cn是n階圈(n≥4),則

引理3[5]如果G有相鄰的 Δ-頂點(diǎn), 則

定義2 一個(gè)雙圈圖G=G[Cm,Cn]滿足:

(1)G是平面圖,且包含一個(gè)m個(gè)頂點(diǎn)的圈Cm=x1x2…xmx1和一個(gè)n個(gè)頂點(diǎn)的圈Cn=y1y2…yny1;

(2)E(G)=E(Cm)∪E(Cn), 以及|V(G)|≤m+n-2;

顯然, 雙圈圖G=G[Cm,Cn]的最大度Δ(G)=4, 最小度δ(G)=2, 且沒(méi)有1度和3度頂點(diǎn). 相對(duì)于圈Cn,如果圈Cm的一條路P(xi,xj)=xixi+1…xj滿足V(Cn)∩V(P(xi,xj))={xi,xj},稱路P(xi,xj)為雙圈圖G的一個(gè)基于圈Cn的耳朵,簡(jiǎn)稱為耳朵,Cn叫做基圈. 如果路P(xi,xj)位于基圈Cn內(nèi)(外),就把路P(xi,xj)叫做內(nèi)(外)耳. 注意到, 雙圈圖G=G[Cm,Cn]的2個(gè)圈相對(duì)于耳朵概念是對(duì)稱的,為可區(qū)分,以下不把圈Cn的路叫做耳朵. 容易觀察到: 雙圈圖G=G[Cm,Cn]至少有2個(gè)耳朵,G的圈Cm是耳朵的并,它的內(nèi)耳數(shù)目等于外耳數(shù)目. 設(shè)基圈Cn的一條路Q=ysys+1…ytyt+1…ykyk+1…yl上連接了G的2個(gè)內(nèi)(外)耳P(ys,yl)?Cm和P(yt,yk)?Cm. 如果在路Q的子路ys+1…yt-1,yt+1…yk-1和yk+1…yl-1上,再?zèng)]有G的其他耳朵,把路P(ys,yl)和P(yt,yk)叫做G的雙(外)耳,不是雙耳的耳朵叫做單耳. 按耳朵分類, 可將雙圈圖分為3類,如圖1所示.

圖1 雙圈圖的類型

定義3 一個(gè)交叉圈是雙圈圖G=G[Cm,Cn],滿足:(1)當(dāng)|V(G)|=m+n-2時(shí),G僅含1個(gè)單內(nèi)耳和1個(gè)單外耳;(2)當(dāng)|V(G)|

推廣定義3如下:

(1)Hk是連通平面圖,且含圈Cn1,Cn2,…,Cnk和Cm;Δ(Hk)=4;

符號(hào)[s,t]表示非負(fù)整數(shù)集{s,s+1,s+2,…,t},其中s和t均為整數(shù),且滿足0≤s

2 主要結(jié)果及其證明

圖中達(dá)到最大度的頂點(diǎn)叫做 Δ-頂點(diǎn).

證明設(shè)f為交叉圈G=G[Cm,Cn] 的一個(gè)鄰點(diǎn)可區(qū)別全染色, 且minf(V(G)∪E(G))=令f(uv)=α.下面分 2 種情形證明.

在H中,僅需考慮對(duì)頂點(diǎn)w以及它的2條關(guān)聯(lián)邊uw和wv進(jìn)行染色,使得新圖H滿足定義H的一個(gè)正常全染色g如下:g(uw)=a1,a1g(wv)=α;g(w)C{α,a1,g(u),g(v)};g(t)=f(t),t(S1{uv})?(S2{uw,w,wv}),其中S1=V(G)∪E(G),S2=V(H)∪E(H).

在H中,僅需考慮對(duì)頂點(diǎn)w以及它的2條關(guān)聯(lián)邊uw和wv進(jìn)行染色,使得新圖H滿足(G).定義H的一個(gè)正常全染色h如下:令h(wv)=b1,b1h(w)=α;h(uw)C{α,b1,h(u),h(ux)};h(t)=f(t),t(S1{uv})?(S2{uw,w,wv}),其中S1=V(G)∪E(G),S2=V(H)∪E(H).

綜合以上討論,引理得證.

□

運(yùn)用相似于引理4的證明方法,可證得

引理6 設(shè)交叉圈G=G[Cm,Cn]不含相鄰的Δ-頂點(diǎn),且每一個(gè)2度頂點(diǎn)都相鄰2個(gè)Δ-頂點(diǎn),則=5.

證明運(yùn)用數(shù)學(xué)歸納法.

下面證明用5種顏色就可以對(duì)G進(jìn)行鄰點(diǎn)可區(qū)別全染色.定義交叉圈G的一個(gè)正常全染色h如下:h(x1)=h(y1)=1,h(x3)=h(y3)=2,h(y2)=h(y4)=4,h(x2)=h(x4)=3,h(y1y2)=h(y3y4)=3,h(y2y3)=1,h(y1y4)=2,h(x1x2)=h(x3x4)=4,h(x2x3)=h(x1x4)=5.

情形2.假設(shè)圈Cm與基圈Cn相交β次,則為便于區(qū)別,用表示圈表示圈Cn,不妨設(shè)見(jiàn)圖2B.由歸納假設(shè),G有一個(gè)鄰點(diǎn)可區(qū)別全染色φ,使得minφ(V(G)∪E(G))=不失一般性,給出G的一個(gè)鄰點(diǎn)可區(qū)別全染色φ如下:φ(xi)=φ(yj)=1,i,j[1,4β]且i,j≡1(mod 4);φ(xi)=φ(yj)=2,i,j[1,4β]且i,j≡3 (mod 4);φ(yj)=4,j[1,4β]e;φ(xi)=3,i[1,4β]e;φ(yjyj+1)=3,j[1,4β]o;φ(yjyj+1)=1,j[1,4β]且j≡2 (mod 4);φ(y1y4β)=φ(yjyj+1)=2,j[1,4β]且j≡0 (mod 4);φ(xixi+1)=4,i[1,4β]o;φ(xixi+1)=φ(x1x4β)=5,i[1,4β]e.

圖2 引理6的相關(guān)圖

綜合以上討論,引理得證.

□

定理1 如果一個(gè)交叉圈G=G[Cm,Cn]不含相鄰的Δ-頂點(diǎn),則

證明情形1.交叉圈G=G[Cm,Cn]不含相鄰的Δ-頂點(diǎn),且每一個(gè)2度頂點(diǎn)都相鄰2個(gè)Δ-頂點(diǎn),由引理6,得

綜合以上討論,定理得證.

□

引理7 設(shè)交叉k-圈Hk(k≥1)不含相鄰的Δ-頂點(diǎn),且每一個(gè)2度頂點(diǎn)都相鄰2個(gè)Δ-頂點(diǎn),則

證明運(yùn)用數(shù)學(xué)歸納法.

由歸納假設(shè),Hk有一個(gè)鄰點(diǎn)可區(qū)別全染色ζ,使得minζ(V(Hk)∪E(Hk))=不失一般性,給出Hk的一個(gè)鄰點(diǎn)可區(qū)別全染色ζ如下:ζ(yi,j)=1,i[1,k],j[1,4β]且j≡1(mod 4);ζ(yi,3)=2,i[1,k],j[1,4β]且j≡3(mod 4);ζ(yi,j)=4,i[1,k],j[1,4β]e;ζ(yi,jyi,j+1)=3,i[1,k],j[1,4β]o;ζ(yi,1yi,4β)=ζ(yi,jyi,j+1)=2,i[1,k],j[1,4β]且j≡0(mod 4);ζ(yi,jyi,j+1)=1,i[1,k],j[1,4β]且j≡2(mod 4);ζ(xi)=1,i[1,2kβ]o;ζ(xi)=2,i[2kβ,4kβ]o;ζ(xi)=3,i[1,4kβ]e;ζ(xixi+1)=4,i[1,4kβ]o;ζ(xixi+1)=ζ(x1x4kβ)=5,i[1,4kβ]e.

圖3 引理7的相關(guān)圖

引理得證.

定理2 如果一個(gè)交叉k-圈Hk(k≥2)不含相鄰的Δ-頂點(diǎn),則

證明情形1.如果交叉k-圈Hk不含相鄰的Δ-頂點(diǎn),且每一個(gè)2度頂點(diǎn)都相鄰2個(gè)Δ-頂點(diǎn),則由引理7,

□

參考文獻(xiàn)：

[1] 周向前, 姚兵, 程輝.關(guān)于0-可旋轉(zhuǎn)樹(shù)[J]. 華南師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2011(4): 54-57.

Zhou X Q,Yao B,Cheng H. On 0-rotatable trees[J].Journal of South China Normal University:Natural Science Edition,2011(4): 54-57.

[2] 吳康, 薛展充. 關(guān)于圈圖Cn的連2距k著色計(jì)數(shù)[J]. 華南師范大學(xué)學(xué)報(bào):自然科學(xué)版, 2007(2): 7-10.

Wu K,Xue Z C.The counting of double distancedk-coloring in cycle[J].Journal of South China Normal University:Natural Science Edition,2007(2): 7-10.

[3] 卜月華, 朱俊蕾. 不含4-圈和7-圈的平面圖的列表均勻染色[J]. 湖南師范大學(xué)自然科學(xué)學(xué)報(bào),2007, 30(4): 6-10.

Bu Y H,Zhu J L.Equitable list coloring of planar graphs without 4- and 7- cycles[J].Journal of Natural Science of Hunan Normal University,2007, 30(4): 6-10.

[4] 魏白, 黃元秋, 郭婷,等. 一類圖在小虧格曲面上的嵌入[J]. 湖南師范大學(xué)自然科學(xué)學(xué)報(bào),2012, 35(5): 24-29.

Wei B,Huang Y Q,Guo T,et al.Embedding on surfaces with small genus of one type of graph[J].Journal of Natural Science of Hunan Normal University,2012, 35(5): 24-29.

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

[6] 姚兵,程輝,姚明,等.圖著色下的樹(shù)頂點(diǎn)鄰集的行為[J].數(shù)學(xué)物理學(xué)報(bào),2011, 31(2): 567-576.

Yao B, Cheng H, Yao M, et al. Behaviors of vertex neighbors of trees under graph colorings[J]. Acta Mathematica Scientia, 2011, 31(2): 567-576.

[7] Wang W F,Wang Y Q. Adjacent vertex distinguishing total coloring of graphs with lower average degree[J]. Taiwanese Journal of Mathematics, 2008, 12(4): 979-990.

[8] Wang Y Q,Wang W F. Adjacent vertex distinguishing total colorings of outerplanar graphs[J]. Journal of Combinatorial Optimization,2010,19(2):123-133.

[9] Hulgan J. Concise proofs for adjacent vetex-distinguishing total colorings[J]. Discrete Mathematics, 2009,309(8): 2548-2550.

[10] Wang H Y. On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ(G)=3[J]. Journal of Combinatorial Optimization, 2007,14(1): 87-109.

[11] Bondy J A,Murty U S R. Graph theory with applications[M]. London, Basingstoke, New York:The MaCmillan Press ltd, 1976.