图的若干参数及算法研究

项目名称： 图的若干参数及算法研究

项目编号： No.61170302

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 计算机科学学科

项目作者： 吕新忠

作者单位： 浙江师范大学

项目金额： 50万元

中文摘要： 图的控制数与染色数是图的两个重要参数，在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用，得到了国内外同行的极大关注。本项目研究图的各种控制数、染色数及其算法，如图的控制数、符号控制数、减符号控制数、图的平方染色、Harmonious染色等。围绕著名的Vizing's猜想和Haynes猜想展开对图的控制数、Harmonious染色的重点研究，力争完全解决Haynes猜想，扩展满足Vizing猜想的图类。给出图的控制数、平方色数、Harmonious色数一些可达的界，对于一些特殊图类计算出符号控制数、平方色数、Harmonious色数的精确值，并设计高效可行的近似多项式时间算法。给出图与其补图的全符号控制数、减符号控制数、Harmonious色数的Nordaus-Gaddum不等式。拟四年内完成论文至少20篇.

中文关键词： 控制数；符号控制数；团符号控制数；L（p;q)-标号；算法

英文摘要：

英文关键词： Domination number；Signed domination number；Signed clique domination number；L（p;q)-labelling；Algorithm