关于积图点可区别边染色的若干结论

运筹学学报 ›› 2013, Vol. 17 ›› Issue (3): 108-114.

关于积图点可区别边染色的若干结论

马刚^1,*, 马效敏², 冶建华¹, 马少仙¹

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

出版日期:2013-09-15 发布日期:2013-09-15
通讯作者: 马刚 E-mail:jsmg@xbmu.edu.cn
基金资助:
国家自然科学基金(No. 61163037), 西北民族大学中央高校基本科研业务费专项资金(No. ZYZ2011082), 西北民族大学中青年科研基金(No. X2007-012)

Some conclusions of vertex-distinguishing edge coloring of product graph

MA Gang^1,*, MA Xiaomin², YE Jianhua¹, MA Shaoxian¹

1. College of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730124, China 2. Scientific Research Department, Northwest University for Nationalities, Lanzhou 730030, China

Online:2013-09-15 Published:2013-09-15

摘要/Abstract

摘要： 如果图G的一个正常边染色满足任意两个不同点的关联边色集不同, 则称为点可区别边染色(VDEC), 其所用最少颜色数称为点可区别边色数. 利用构造法给出了积图点可区别边染色的一个结论, 得到了关于积图点可区别边色数的若干结果, 并且给出25个具体积图的点可区别边色数, 验证了它们满足点可区别边染色猜想(VDECC).

关键词: 积图, 联图, 点可区别边染色, 点可区别边色数

Abstract: A proper edge coloring of graph G is called vertex-distinguishing if the set of colors meets to vertex u differs from the set of colors meets to vertex v for any two distinct vertices u and v. The minimum number k for which there exists vertex distinguishing proper edge coloring using k colors is called the vertex distinguishing proper edge chromatic number. In this paper, we will obtain a conclusion of vertex-distinguishing edge coloring of product graph by using the method of construction, and get some results of the vertex-distinguishing edge chromatic numbers of product graphs, then obtain vertex-distinguishing edge chromatic numbers of 25 product graphs, which satisfy the conjecture on VDECC.

Key words: product graph, join-graph, vertex-distinguishing edge coloring, vertex-distinguishing edge chromatic number

中图分类号:

O157.5

马刚, 马效敏, 冶建华, 马少仙. 关于积图点可区别边染色的若干结论[J]. 运筹学学报, 2013, 17(3): 108-114.

MA Gang, MA Xiaomin, YE Jianhua, MA Shaoxian. Some conclusions of vertex-distinguishing edge coloring of product graph[J]. Operations Research Transactions, 2013, 17(3): 108-114.

参考文献

Bazgan C, Harkat-Benhamdine A, Li H, et al. On the vertex-distinguishing proper edge-colorings of graphs [J]. J of Combine Theory (Ser B), 1999, 75: 288-301.
Burris A C, Schelp R H. Vertex-distinguishing proper edge-colorings [J]. J of Graph Theory, 1997, 26(2): 73-82.
Zhang Z F, Li J W, Chen X E, et al. D(\beta)-vertex-distinguishing proper edge-coloring of graphs [J]. Acta Mathematica Sinica (Chinese Ser), 2006, 49(3): 703-708.
Zhang Z F, Liu L Z, Wang J F. Adjacent strong edge coloring of graphs [J]. Applied Mathematics Letters, 2002, 15: 623-626.
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.
Chen X E, Gao Y P. Vertex-distinguishing proper edge-coloring chromatic numbers of the composition of two graphs [J]. J of Jilin University (Science ed.), 2011, 49(2): 207-212.
Rudasova J, Sotak R. Vertex-distinguishing proper edge coloring of some regular graphs [J]. Discrete Mathematics, 2008, 308(5/6): 795-802．
Ma G, Ma S X, Zhang Z F. On the vertex-distinguishing edge chromatic number of P_m W_n [J]. J of Lanzhou University (Natural Sciences), 2007, 43(2): 103-106.
Zhang Z F, Li J W, Zhao CC, et al. On the vertex-distinguishing-equitable edge chromatic of some join-graphs [J]. Acta Mathematica Sinica (Chinese Ser), 2007, 50(1): 197-204.
Wang Z W, Zhang Z F, Yan L H. Vertex-distinguishing edge chromatic number of P_m P_n [J]. J of Lanzhou University (Natural Sciences), 2005, 41(6): 100-101.
Tian S L, Chen P. On the vertex-distinguishing edge colorings of some product graphs [J]. J of Shandong University (Science ed.), 2006, 41(4): 53-56.
Yap H P. Total Colorings of Graphs [M]. Lecture Notes in Mathematics, 1623, Berlin: Springer, 1996.
Bondy J A, Murty U S R. Graph Theory with Applications [M]. New York: The Macmillan Press Ltd, 1976.

[1]	吕雪征, 魏二玲, 宋宏业. 联图的圈基[J]. 运筹学学报, 2018, 22(4): 148-152.
[2]	苏振华. 六阶图C_6+3K_2与P_n, C_n的联图交叉数[J]. 运筹学学报, 2017, 21(3): 23-34.
[3]	周志东, 李龙 . 一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数[J]. 运筹学学报, 2016, 20(4): 115-126.
[4]	周志东，王晶. W₆*S_n的交叉数[J]. 运筹学学报, 2013, 17(2): 10-18.