圖M(Sn)和M(Fn)的點可區(qū)別均勻邊色數(shù)

馬剛, 馬少仙, 馬效敏

(1.西北民族大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,甘肅 蘭州 730124;2.西北民族大學(xué)科研處,甘肅 蘭州 730030)

圖M(Sn)和M(Fn)的點可區(qū)別均勻邊色數(shù)

馬剛1, 馬少仙1, 馬效敏2

(1.西北民族大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,甘肅 蘭州 730124;2.西北民族大學(xué)科研處,甘肅 蘭州 730030)

如果圖G的一個正常邊染色滿足任意兩個不同點的關(guān)聯(lián)邊色集不同,且任意兩種顏色所染邊數(shù)目相差不超過1,則稱為點可區(qū)別均勻邊染色(VDEEC),其所用最少染色數(shù)稱為點可區(qū)別均勻邊色數(shù).本文用構(gòu)造法研究了一些Mycielski圖的點可區(qū)別均勻邊染色,得到了星和扇的Mycielski圖的點可區(qū)別均勻邊色數(shù),驗證了它們滿足點可區(qū)別均勻邊染色猜想.

Mycielski圖;點可區(qū)別均勻邊染色;點可區(qū)別均勻邊色數(shù)

1 引言及定義

由信息科學(xué)、計算機科學(xué)、生物學(xué)等提出的點可區(qū)別邊染色(或強邊染色)[12]是一個十分困難的問題,文獻 [3]提出了距離不超過 β的任意兩點可區(qū)別的邊染色概念及相關(guān)猜想.文獻[4]中又提出了圖的點可區(qū)別均勻邊染色概念和猜想,得到了星、完全圖、扇、輪和完全二部圖等簡單圖的點可區(qū)別均勻邊色數(shù).文獻[5]探討了一些倍圖的均勻鄰強邊色數(shù),文獻[6]得到了等階的路和路,路和圈,圈和圈的聯(lián)圖的點可區(qū)別均勻邊色數(shù).文獻[7]討論了一些Mycirelski圖的均勻鄰強邊色數(shù),本文給出了星Sn和扇Fn的Mycielski圖的點可區(qū)別均勻邊色數(shù).

2 主要結(jié)果

[1]Bazgan C,Harkat-Benhamdine A,Li H,et al.On the vertex-distinguishing proper edge-colorings of graphs[J]. J.of Combin.Theory,Ser.B,1999,75:288-301.

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

[3]張忠輔,李敬文,陳祥恩,等.圖的距離不大于β的任意兩點可區(qū)別的邊染色[J].數(shù)學(xué)學(xué)報,2006,49(3):703-708.

[4]Zhang Z F,Li M C,Yao B,et al.On the vertex distinguishing equitable edge-coloring of graphs[J].ARS Combinatoria,2008,86:193-200.

[5]馬剛,張忠輔.若干圖的倍圖的均勻鄰強邊染色[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(1):64-68.

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

[7]馬效敏,馬剛,張忠輔.一些圖的Mycielski圖的均勻鄰強邊染色[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(4):581-586.

[8]Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:The Macmillan Press Ltd.,1976.

On vertex-distinguishing-equitable edge chromatic number of M(Sn)and M(Fn)graph

Ma Gang1,Ma Shaoxian1,Ma Xiaomin2
(1.College of Mathematics and Computer Science,Northwest University for Nationalities, Lanzhou 730124,China;
2.Scienti fi c Research Department,Northwest University for Nationalities,Lanzhou 730030,China)

A proper edge coloring of graph G is called vertex-distinguishing-equitable edge coloring(VDEEC) if colored sets from any two vertices incident edge are di ff erent,and the number of edges in any two color classes di ff er by at most one,which the required minimum number of colors is called the vertex-distinguishing-equitable edge chromatic number.In this paper,we obtain the vertex-distinguishing-equitable edge chromatic numbers of mycielski graphs of star and fan by using constructive method,which satisfy the conjecture on VDEEC.

mycielski graph,vertex-distinguishing-equitable edge coloring, vertex-distinguishing-equitable edge chromatic number

O157.5

A

1008-5513(2012)05-0580-05

2011-12-03.

西北民族大學(xué)中央高校基本科研業(yè)務(wù)費專項資金(ZYZ2011082);西北民族大學(xué)中青年科研項目(X2007-012).

馬剛(1975-),副教授,研究方向：圖論及其應(yīng)用.

2010 MSC:05C15