星、扇、輪的聯(lián)圖的點可區(qū)別均勻邊色數(shù)*

朱俊俏, 卜月華

(浙江師范大學(xué) 行知學(xué)院,浙江 金華 321004)

0 引 言

圖論在自然科學(xué)和應(yīng)用科學(xué)中都起著重要的作用,如網(wǎng)絡(luò)設(shè)計、計算機科學(xué)、信息科學(xué)、密碼學(xué)、DNA基因譜的確定和計數(shù)、工業(yè)生產(chǎn)和企業(yè)管理中的優(yōu)化方法等都廣泛地應(yīng)用了圖論及其算法[1].圖的染色理論是圖論研究的熱點問題,它起源于四色定理,之后許多學(xué)者研究了列表染色、均勻染色[2-4]、強鄰邊染色[5-6],其中點可區(qū)別全染色[7]、點可區(qū)別邊染色[8-9]或點可區(qū)別均勻邊染色[10-11]等帶有限制條件的染色，是一類較難研究的問題.文獻[10]解決了一些路、圈聯(lián)圖的點可區(qū)別邊染色;文獻[11]給出了星、扇、輪、完全二部圖等特殊圖類的點可區(qū)別均勻邊色數(shù).本文得到了星、扇、輪的聯(lián)圖的點可區(qū)別均勻邊色數(shù).

定義1[1]對簡單圖G和正整數(shù)k,若存在映射f:E(G)→{1, 2,…,k},滿足任意相鄰的2條邊e,e′, 有f(e)≠f(e′),則稱f為G的一個k-正常邊染色,并記χ′(G)=min{k|G的k-正常邊染色}為G的邊色數(shù).

猜想2[10-11]對于|V(G)|≥3的簡單連通圖G,有

猜想2中1)的左端是顯然的.設(shè)Sn,Fn,Wn分別是n+1階的星、扇、輪圖,本文得到了Sn∨Sn,Fn∨Fn,Wn∨Wn的點可區(qū)別均勻邊色數(shù).文中未加說明的術(shù)語請參考文獻[10].

1 主要結(jié)果

在下面的一些運算中,若其結(jié)果大于2n+2,則取模2n+2.

1)若n=1,S1∨S1=K4,則由文獻[1]知結(jié)論為真.

2)若n=2,S2∨S2=P3∨P3,則由文獻[10]知結(jié)論為真.

①n≡0(mod 2).定義f為:

對f,有:

從而Sn∨Sn中任意2個頂點有不同的色集,故f是Sn∨Sn的一個(2n+2)-VDEC.又

故f是Sn∨Sn的一個(2n+2)-VDEEC.

②n≡1(mod 2).當n=5時,f的定義如表1所示.此時易知f是一個12-正常邊染色,且S5∨S5中任意2個頂點有不同的色集,故f是S5∨S5的一個12-VDEC.對|Ei|,當i∈{6,8}時,|Ei|=3;當i?{6,8}時,|Ei|=4.故f是S5∨S5的一個12-VDEEC.

表1 S5∨S5的一個12-VDEEC

當n≥7時,f定義為:

此時對f,有:

表2 S4∨S4的一個10-VDEEC

1)若n=1,F1∨F1=K4,則由文獻[1]知結(jié)論為真.

2)若n=2,F2∨F2=C3∨C3,則由文獻[8]知結(jié)論為真.

①n≡0(mod2).當n=4時,定義f如表2所示.

從而Fn∨Fn中任意2個頂點有不同的色集,故f是Fn∨Fn的一個(2n+2)-VDEC.又

故f是Fn∨Fn的一個(2n+2)-VDEEC.

當n≥7時,定義f為:

其余邊所染的顏色同定理1中的②.對f,有:

從而Fn∨Fn中任意2個頂點有不同的色集,故f是Fn∨Fn的一個(2n+2)-VDEC.又

故f是Fn∨Fn的一個(2n+2)-VDEEC.定理2證畢.

表3 S4∨S4的一個10-VDEEC

1)若n=1,W1∨W1=K4,則由文獻[1]知結(jié)論為真.

2)若n=2,W2∨W2=C3∨C3,則由文獻[8]知結(jié)論為真.

故f是Wn∨Wn的一個(2n+2)-VDEEC.

其余的點所染的色集同定理2中的②.從而Wn∨Wn中任意2個頂點有不同的色集,故f是Wn∨Wn的一個(2n+2)-VDEC.又

故f是Wn∨Wn的一個(2n+2)-VDEEC.定理3證畢.

參考文獻：

[1]Bondy J A,Murty U S R.Graph theory with applications[M].New York:Macmillan London and Elsevier,1976.

[2]Zhu Junlei,Bu Yuehua.Equitable list colorings of planar graphs without short cycles[J].Theoretical Computer Science,2008,407(1):21-28.

[3]Zhu Junlei,Bu Yuehua.Equitableand equitable list colorings of graphs[J].Theoretical Computer Science,2010,411(43):3873-3876.

[4]Bu Yuehua,Lu kai.List injective coloring of planar graphs with girth 5,6,8 original[J].Research Article Discrete Applied Mathematics,2013,161:1367-1377.

[5]Favaron O,Li Hao,Schelp R H.Strong edge coloring of graphs[J].Dscrete Mathematics,1996,159(1):103-109.

[6]Zhang Zhongfu,Liu Linzhong,Wang Jianfang.Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters,2002,15(5):623-626.

[7]朱俊俏,卜月華.2-連通外平面圖的鄰點可區(qū)別全染色[J].浙江師范大學(xué)學(xué)報:自然科學(xué)版,2009,32(1):33-39.

[8]Burris A C,Schelp R H.Vertex-distinguishing proper edge-colorngs[J].Journal of Graph Theory,1997,26(2):73-82.

[9]Bazgan C,Benhamdine A H,Li Hao,et al.On the vertex-distinguishing proper edge-colorings of graphs[J].Journal of Combinatorial Theory:Series B,1999,75(2):288-301.

[10]張忠輔,李敬文,趙傳成,等.若干聯(lián)圖的點可區(qū)別均勻邊染色[J].數(shù)學(xué)學(xué)報,2007,50(1):197-204.

[11]Zhang Zhongfu,Li Muchun,Yao Bing,et al.On the vertex-distinguishing equitable edge-coloring of graph[J].Ars Combinatoria,2008,86:193-200.