图M(Sn)和M(Fn)的点可区别均匀边色数

马刚, 马少仙, 马效敏

(1.西北民族大学数学与计算机科学学院,甘肃 兰州 730124;2.西北民族大学科研处,甘肃 兰州 730030)

图M(Sn)和M(Fn)的点可区别均匀边色数

马刚1, 马少仙1, 马效敏2

(1.西北民族大学数学与计算机科学学院,甘肃 兰州 730124;2.西北民族大学科研处,甘肃 兰州 730030)

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同,且任意两种颜色所染边数目相差不超过1,则称为点可区别均匀边染色(VDEEC),其所用最少染色数称为点可区别均匀边色数.本文用构造法研究了一些Mycielski图的点可区别均匀边染色,得到了星和扇的Mycielski图的点可区别均匀边色数,验证了它们满足点可区别均匀边染色猜想.

Mycielski图;点可区别均匀边染色;点可区别均匀边色数

1 引言及定义

由信息科学、计算机科学、生物学等提出的点可区别边染色(或强边染色)[12]是一个十分困难的问题,文献 [3]提出了距离不超过 β的任意两点可区别的边染色概念及相关猜想.文献[4]中又提出了图的点可区别均匀边染色概念和猜想,得到了星、完全图、扇、轮和完全二部图等简单图的点可区别均匀边色数.文献[5]探讨了一些倍图的均匀邻强边色数,文献[6]得到了等阶的路和路,路和圈,圈和圈的联图的点可区别均匀边色数.文献[7]讨论了一些Mycirelski图的均匀邻强边色数,本文给出了星Sn和扇Fn的Mycielski图的点可区别均匀边色数.

2 主要结果

[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]张忠辅,李敬文,陈祥恩,等.图的距离不大于β的任意两点可区别的边染色[J].数学学报,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].纯粹数学与应用数学,2010,26(1):64-68.

[6]张忠辅,李敬文,赵传成,等.若干联图的点可区别均匀边色数[J].数学学报,2007,50(1):197-204.

[7]马效敏,马刚,张忠辅.一些图的Mycielski图的均匀邻强边染色[J].纯粹数学与应用数学,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.

西北民族大学中央高校基本科研业务费专项资金(ZYZ2011082);西北民族大学中青年科研项目(X2007-012).

马刚(1975-),副教授,研究方向：图论及其应用.

2010 MSC:05C15