图的生成连通性及相关问题研究

The spanning connectivity and the wide diameter are concepts introduced in recent years. The spanning connectivity is the generalization and combination of the classic connectivity and hamiltonicity such that the connectivity and hamiltonicity are special cases of the spanning connectivity, and the wide diameter is a notion based connectivity and it plays an important role in the design and implementation of parallel and effective information trasportation in interconnected networks. There are only some preleminary results on the above two problems and most of them focused on some special networks, for general graphs a lot of corresponding problems are still open. In this project, we shall use the tools of graph theory, combinatorics, algebra and probablity theory to thoroughly explore the spanning connectivity and wide diameter problems of general graphs. We shall try to obtain the conditions for the existence of some specied spanning connectivity and wide diameter of genereal graphs so that generalize some classical results in graph theory. Also we shall try to apply the known and the new results of us on spanning connectivity and wide diameter to networks to get some deeper and more significant properties of some important networks.

图的生成连通性以及宽直径等是近年来提出的概念，其中图的生成连通性是图的经典连通性和哈密尔顿性的推广和融合，使得经典的连通性和哈密尔顿性成为生成连通性的特殊情况，而图的宽直径则是在图的连通性概念的基础上提出来的一个概念，在大型互联网络系统的并行及有效信息传输方法的设计与实现中起着重要作用，在生物信息和神经信息等中都有相当的应用. 以上两个问题目前只有一些初步的结果，主要集中在几类特殊网络的此类性质的研究上，一般图的相应问题仍有待研究. 本项目将综合应用图论、组合数学、代数学及概率论的工具，深入研究一般图生成连通性和直径以及相关的问题，给出一般图类的特定生成连通度存在的条件，推广图论中已知的经典结果. 我们将应用生成连通性和宽直径的已知结果以及我们可能获得的有关一般图的最新结论，来研究各种常见重要网络的这两个性质，力争得到一些深刻而重要的结果.

依照申请书的研究内容和计划，开展了相关的研究，基本上完成了预定的研究任务。研究的主要内容图的生成连通性问题，包括图的生成可圈性问题，一些重要网络的可系性问题（即二部图的生成连通性质）和它们的广义连通性质，图的超欧拉性质和哈密尔顿性质（即图的边生成连通性质和特殊的点生成连通性质），一般图和一些特殊图的一些与生成连通性有关的指标的性质（包括它们的紧的界和重要性质的研究）等。项目组四年来共完成论十余篇其中已发表论文十一篇（其中接受待发表一篇），其中五篇是发表在SCI国际性杂志上。四年来共有八名硕士研究生毕业，他们的毕业论文均与本项目的研究内容有关。现有在读硕士研究生3名其中一人将于2018年毕业。我们的成果有以下几个方面。.一般图的生成可圈性问题，我们给出了图的点数和边数满足一定条件时，图是生成可圈的，把已有的已有特殊结果推广到了一般的情形。.一些重要网络的生成连通性问题，包括证明了对换网络的极大可系性，超立方体加边后为k-生成连通的最小边数，超立方体和折叠超立方体的结构容错性质以及条件容错的平衡超立方体的Menger连通性，为更优网络的设计提供了理论依据。.图的超欧拉性和哈密尔顿性，包括3-边连通周长不超过11图有生成欧拉子图的充要条件，具有某些禁止子图的3-连通图是哈密尔顿图的充要条件。.图的与连通性和哈密尔顿性有关的参数的性质和界的研究，包括图的独立横贯支配数的界和重要性质的研究，直积图的坚韧度和边坚韧度以及树和单圈图的Co-PI指标的界的研究等。.具有特殊性质的图的拉普拉斯特征值的研究，证明了恰有两个拉普拉斯特征值大于2的图是拉普拉斯谱唯一的以及刻画了具有较小的第二大拉普拉斯特征值的图类等。