張東翰

（商洛學(xué)院 數(shù)學(xué)與計算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

圖Dn,4的鄰點強可區(qū)別的全染色

張東翰

（商洛學(xué)院 數(shù)學(xué)與計算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

通過分析圖Dn,4的結(jié)構(gòu)，利用窮舉法和組合分析法討論了圖Dn,4的鄰點強可區(qū)別的全染色，通過構(gòu)造具體染色得到了圖Dn,4的鄰點強可區(qū)別的全色數(shù)。從而證明了圖Dn,4的鄰點強可區(qū)別的全色數(shù)是存在的。

窮舉法；組合分析法；色數(shù)

張忠輔教授提出了圖的鄰點強可區(qū)別的全染色的概念[1]，隨后很多學(xué)者對其進(jìn)行了研究，迄今，劉永平等[2]給出了Pn×Pm的鄰點強可區(qū)別的全染色，盧建立等[3]給出了中間圖的鄰點強可區(qū)別的全染色，郭旭衛(wèi)等[4-5]給出了一類Pm×Cn圖和D(Pn)圖的鄰點強可區(qū)別的全染色，鄭純等[6]給出了扇和輪的鄰點強可區(qū)別的全染色，張效賢[7]給出了C3m×C3n、C4m×C4n的鄰點強可區(qū)別的全染色，但是，由于此染色的難度比較大，相關(guān)結(jié)果并不是很多，通過對大量文獻(xiàn)的研讀，研究了圖Dn,4的鄰點強可區(qū)別的全染色。

1 預(yù)備知識

定義1[1]設(shè)G(V,E)是階數(shù)不小于3的簡單連通圖，k是自然數(shù)，f是從V(G)∪E(G)到{1,2,…,k}的映射，如果滿足：

1)對任意的邊uv∈E(G)，f(u)≠f(v)，f(u)≠f(uv)≠f(v)；

2)對任意的兩相鄰的邊uv,uw∈E(G)(v≠w)，f(uv)≠f(uw)；

3)對任意的邊uv∈E(G)，其端點的色集合滿足C(u)≠C(v)，其中任一頂點v的色集合為C(u)={f(u)}∪{f(v)｜uv∈E(G)}∪{f(uv)｜uv∈E(G)}。則稱f為圖G的一個鄰點強可區(qū)別的全染色，（簡記為k-AVSDTC），且稱數(shù)χast(G)=min{k｜k-AVSDTC}為G為的鄰點強可區(qū)別的全色數(shù)。

定義2[8]由點集V(Dn,4)={v0,v11,v12,v13,v21,v22, v23,…,vn1,vn2,vn3}和邊集E(Dn,4)={v0v11,v11v12,v12v13, v13v0,v0v21,v21v22,v22v23,v23v0,…,v0vn1,vn1vn2,vn0v0}所形成的圖，記為Dn,4。

引理1[1]設(shè)圖G是階不小于3的圖，有χast(G)≥Δ+1；若G有相鄰的兩個最大度點，則χast(G)≥Δ+2，其中Δ代表圖G的最大度。

本文中未加敘述的術(shù)語、記號可在文獻(xiàn)[9-15]中找到。

2 定理及其證明

定理1對于圖Dn,4，有。

證明當(dāng)n=1時，此時圖是一個4階的圈，根據(jù)文獻(xiàn)[1]可知χast(Dn,4)=5。

當(dāng)n≥2時，由于沒有相鄰的最大度點，所以根據(jù)引理1可知χast(Dn,4)≥2n+1，現(xiàn)給出一個(2n+ 1)-AVSDTC，設(shè)色集合C={1,2,3,…，2n，2n+1}。

對于邊v0v11,v0v13,v0v21,v0v23,…,v0vn1,v0vn3,分別用色1,2,3,…，2n染，對于邊vi1vi2,vi2vi3分別用色1,2染(i=2,3,…，n)，對于邊v11v12,v12v13分別用色3,4染。

對于點v0,vi2(i=1,2,…，n)都用色2n+1染，對于點vi1,vi3(i=1,2,…，n)分別用色4,3染,則此染色法顯然是一個正常的全染色，又由于C(v0)={1,2,3,…,2n,2n+1}，C(v11)={1,3,4,2n,2n+1}，C(v12)={3,4,2n+1}，C(v13)={2,3,4,2n+1}，C(vi1)={1,4,2i-1,2n+1}，C(vi2)={1,2,3,4,2n+1}，C(vi3)={2,3,2i,2n+1}，(i=2,3,…，n)。因此該染色法是一個(2n+1)-AVSDTC，即χast(Dn,4)=2n+1。

[1]張忠輔,程 輝，姚 兵.圖的鄰點強可區(qū)別的全染色[J].中國科學(xué)：A輯,2007,37(9)：1073-1082.

[2]劉永平,張 銳,蘇旺輝,等.Pn×Pm的鄰點強可區(qū)別的全染色[J].蘭州理工大學(xué)學(xué)報,2007,33(2)：164-167.

[3]盧建立,任鳳霞,馬美琳.中間圖的鄰點強可區(qū)別的全染色[J].河南師范大學(xué)學(xué)報：自然科學(xué)版,2012,40(5)：112-114.

[4]郭旭衛(wèi),馬 剛,馬少仙.一類Pm×Cn圖的鄰點強可區(qū)別全染色[J].貴州大學(xué)學(xué)報：自然科學(xué)版,2009,26(2)：24-26.

[5]郭旭衛(wèi),馬少仙.D(Pn)圖的鄰點強可區(qū)別全染色[J].甘肅聯(lián)合大學(xué)學(xué)報：自然科學(xué)版,2009,23(5)：24-25.

[6]鄭 純,劉煥平.扇和輪的鄰點強可區(qū)別全染色[J].哈爾濱師范大學(xué)學(xué)報：自然科學(xué)版,2009,25(5)：33-34.

[7]張效賢.C3m×C3n、C4m×C4n的鄰點強可區(qū)別全染色及全色數(shù)[J].甘肅科學(xué)學(xué)報,2009,21(2)：26-28.

[8]孫婷婷.圖的點可區(qū)別的邊染色及點可區(qū)別的全染色[D].重慶：重慶大學(xué),2008.

[9]王彥妮,王麗偉,劉 萍.幾類圖的鄰點可區(qū)別的全染色[J].科學(xué)技術(shù)與工程,2007,7(13)：3048-3051.

[10]閆麗紅,王治文,張忠輔.θ-廣義圖的鄰點可區(qū)別的全染色[J].經(jīng)濟(jì)數(shù)學(xué),2007,24(1)：103-106.

[11]陳祥恩,張忠輔.Pm∨Pn的鄰點可區(qū)別的全染色[J].西北師范大學(xué)學(xué)報,2005,41(1)：13-15.

[12]張東翰.蛛形圖的全染色和星全染色[J].商洛學(xué)院學(xué)報,2013,27(6)：31-32.

[13]張東翰,朱 白.路的D(3)-點可區(qū)別的全染色[J].商洛學(xué)院學(xué)報,2014,28(2),11-12.

[14]Bondy J A,Murty U S R.Graph theory with Applications[M].New York：The Macmillan Press Ltd, 1976.

[15]Reinhard D.Graph theory[M].New York：Springer-Verlag,1997.

（責(zé)任編輯：李堆淑）

Adjacent Vertex Strongly Distinguishing Total Coloring of Graph Dn,4

ZHANG Dong-han
(College of Mathematics and Computer Application,Shangluo University,Shangluo 726000,Shaanxi)

Through the analysis of graph Dn,4,the adjacent vertex strongly distinguishing total coloring of graph Dn,4is discussed by the exhaustion method and the combination analytic method.The adjacent vertex strongly distinguishing total chromatic number of graph Dn,4is gained by construction specific coloring,thus,the adjacent vertex strongly distinguishing total chromatic number of graph Dn,4is existent.

method of exhaustion;combination analytic method;chromatic number.

O157.5

：A

：1674-0033（2014）06-0008-02

10.13440/j.slxy.1674-0033.2014.06.003

2014-09-23

陜西省教育廳專項科研計劃項目（14JK1225）

張東翰，男，河北邢臺人，碩士，講師