图中路和圈的嵌入问题及相关研究

随着信息科学和计算机科学技术的迅猛发展，图论和组合数学作为其重要理论基础得到国际数学界和理论计算机科学界的高度重视和广泛研究，图论的思想和方法在网络设计和分析中的应用越来越被科研工作者认可和采用。本项目从图的结构性质入手，在现有工作基础上，深入研究以下几个问题:（一）研究容错网络图的路和圈的嵌入问题，力争解决或部分解决最近提出的关于容错超立方体网络圈嵌入问题的一个猜想。（二）支撑连通度是新引入的与路的嵌入问题相关的一个参数，研究一些著名网络图类(如arrangement graph，exchanged hypercube)的支撑连通度。（三）探索支撑连通度与经典连通度之间的关系，试图推广经典连通度的一些结果（如一些重要的不等式）到支撑连通度的情形。本项目所研究的问题大多是国际著名学术刊物上提出的新问题，这些研究不仅丰富图论研究内容，也为大规模互连网络的设计和性能分析提供理论依据。

本项目从图的结构性质入手,主要研究一些网络图类的路和圈的嵌入问题、连通性问题、图的控制数、图的重构数及图的杂色子图划分等问题。解决了故障点和边存在的情况下的局部纽立方体中的路的可嵌入问题；确定了金字塔网的对称性、连通度及在有故障点存在的情况下圈的可嵌入问题；确定了交换超立方体网络的距离性质，如它的Wiener指标，平均距离，宽直径，容错直径等；给出了交换超立方体网络控制数的上下界；确定了整数单纯形的宽直径和容错直径；确定了双星图、完全多部图及其补图的重构数和一致重构数；确定了r边染色的完全三部图的杂色树的划分数，并给出计算公式；确定了r边染色的完全图的杂色树的划分数，并给出多项式算法；确定了r边染色的完全多部图的杂色树的划分数的上下界。本项目所得结果均是创新性研究成果。至今完成学术论文12篇，其中被SCI检索收录的有9篇，其余3篇已经投稿,圆满完成了本课题所预定的研究任务。