计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (16): 26-29.

• 理论研究、研发设计 • 上一篇    下一篇

随机图的点可区别V-全染色算法

胡腾云,尹  波,代素敏,李敬文   

  1. 兰州交通大学 电子与信息工程学院,兰州 730070
  • 出版日期:2015-08-15 发布日期:2015-08-14

Algorithm for vertex distinguishing V-total coloring of graphs

HU Tengyun, YIN Bo, DAI Sumin, LI Jingwen   

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
  • Online:2015-08-15 Published:2015-08-14

摘要: 图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过[O(n3)]。

关键词: 图, 点可区别V-全染色, 点可区别V-全色数

Abstract: For vertex distinguishing V-total coloring of graph [G], the colors of both adjacent edges and vertex with its incident edges should be different. Moreover, the color sets of any vertices are not the same. The minimum coloring number is called the vertex-distinguishing V-total chromatic number of [G]. This paper presents a heuristic algorithm for vertex distinguishing V-total coloring according to its constrain rules. The algorithm iterates gradually in proper sequence with the help of the color matrix and complementary set. When the generic function value meets the requirement, we say that the current coloring is successful. This paper gives a detail description of the algorithm, algorithm analysis and algorithm testing results, and also verifies the vertex distinguishing V-total coloring conjecture of graphs with given points. The experimental results show that the algorithm has good efficiency and can obtain the vertex distinguishing V-total chromatic number of graphs, and the time complexity of the algorithm is not more than[O(n3)].

Key words: graphs, vertex-distinguishing V-total coloring, vertex-distinguishing V-total chromatic number