廣義Mycielski圖的鄰點(diǎn)可區(qū)別的非正常全染色

劉利群

(長江大學(xué) 信息與數(shù)學(xué)學(xué)院,湖北 荊州 434023)

1 引言

染色問題是圖論中具有重要實(shí)際意義和理論意義的研究課題之一．本文考慮的圖均為沒有孤立邊,最多有一個(gè)孤立點(diǎn)的有限無向單圖. 2004年,張忠輔和陳祥恩等人引入了圖的鄰點(diǎn)可區(qū)別的全染色的概念[1],許多學(xué)者對(duì)圖的鄰點(diǎn)可區(qū)別的全染色的理論作了大量的研究. 2005年,文獻(xiàn)[2]提出了圖的鄰點(diǎn)可區(qū)別非正常邊色數(shù)及全色數(shù)(一般鄰點(diǎn)可區(qū)別色指標(biāo))的概念(General neighbour-distinguishing index of a graph).另外,文中一些其他術(shù)語及符號(hào)參見文獻(xiàn)[3].

下面給出一些相關(guān)概念:

定義1[1]對(duì)階數(shù)至少為2的連通圖G(V,E),令f為從V(G)∪E(G)到{1,2,…,k}的映射,其中k為正整數(shù).對(duì)任意的u∈V(G),C(u)表示{f(u)∪f(uv|uv∈E(G))}.如果f滿足下面的條件

1)對(duì)任意的uv,vw∈E(G),u≠v,有f(uv)≠f(vw),

2)對(duì)任意的uv∈E(G),u≠v,有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv)則稱f為圖G的一個(gè)k-正常全染色.如果f為圖G的一個(gè)k-正常全染色,并滿足

3)對(duì)任意的uv∈E(G),有C(u)≠C(v),則稱f為圖G的一個(gè)k-鄰點(diǎn)可區(qū)別全染色(簡記為k=AVDTC).

定義2[2]對(duì)圖G(V,E)，映射F∶E(G)∪V(G)→{1,2,…,k}滿足對(duì)任意u,v∈V(G)，uv∈E(G)有C(u)≠C(v)，則稱f是G的鄰點(diǎn)可區(qū)別的非正常全染色或一般鄰點(diǎn)可區(qū)別全染色,簡記為gndt-染色.并稱gndti(G)=min{k|G有k-gndt-染色}為G的鄰點(diǎn)可區(qū)別的非正常全色數(shù)或一般鄰點(diǎn)可區(qū)別色指標(biāo)(general neighbour-distinguishing index of a graph).

定義3[4]設(shè)G是頂點(diǎn)集合為V(G)={v0i|i=1,2,…,p}的簡單圖，n是正整數(shù)，稱Mn(G)為G上的錐(或廣義Mycielski圖)，如果

V(Mn(G))={v01,v02,…,v0p;v11,v12,…
,v1p,…,vn1,vn2,…,vnp,w},

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

證明 令V(Pm)={v01,v02,…,v0m},E(Pm)={v01v02,v02v03…,,v0(m-1)v0m},

V(Mn(Pm)/{w})={v01,v02,…,v0m,
v11,v12,…,v1m,…,vn1,…,vnm},

若f(v01v02)=1,f(v02v03)=2,則f(v03v04)=2,f(v03v01)=2,則v01與v02的色集合相同,這與它們是鄰點(diǎn)可區(qū)別的相矛盾.其他染法類似可推出矛盾.

g(vij)=1,i∈{0,1,…,n},j≡1(mod3);
g(vij)=2,i∈{0,1,…,n},j≡3(mod3);
g(vij)=3,i∈{0,1,…,n},j≡0(mod3);

2)再重新給點(diǎn)染色,當(dāng)g(u)=1時(shí),令f(u)=2;當(dāng)g(u)=2時(shí),令f(u)=3;當(dāng)g(u)=3時(shí),令f(u)=1;

證明 令V(Pm)={v01,v02,…,v0m},E(Pm)={v01v02,v02v03…,,v0(m-1)v0m},

V(Mn(Pm)/{w})={v01,v02,…,v0m,
v11,v12,…,v1m,…,vn1,…,vnm},

當(dāng)g(vni)=1時(shí),令f(vniw)=2;當(dāng)g(vni)=2時(shí),令f(vniw)=3;當(dāng)g(vni)=3時(shí),令f(vniw)=1(i=1,2,…,m).

頂點(diǎn)w可染其中任一顏色.

參考文獻(xiàn)：

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

[2]Grorie, Hornak M, Palmer C,et al.General neighbour-distinguishing index of a graph [J].Discrete Mathematics, Special Issue devoted to BBS,2005.

[3] Bondy J A,Murty U S R. Graph Theory with Applications[M].London:Macmillan Press Ltd,1976.

[4] Tardif C.Fraetional chromatic numbers of cones over graphs [J].Graph Theory, 2001,38:87-94.

[5]Zhang Zhong-fu, Liu Lin-zhong, Wang Jian-fang. Adjacent Strong Edge Coloring of Graphs[J].Applied Mathematics Letters,2002,15(5).

[6]劉利群,陳祥恩.路和圈上的錐的D(2)-點(diǎn)可區(qū)別正常邊染色[J].山東大學(xué)學(xué)報(bào),2008,43(2):87-97.

[7]Balister P N,Riordan O M,Schelp R H, Vertex-distinguishing edge colorings of graphs[J]. Graph Theory 42,2003,95-109.

[8] Bazgan C,Harkat-Benhamdine A,Li Hao,et al, On the vertex-distinguishing edge colorings of graphs[J].J of Combin Theory,1999,75.

[9]Balister P N, Bollobás B and Schelp R H, Vertex distinguishing colorings of graphs with△(G)=2 [J].Discrete Mathematics, 2002,252.