斯坦纳树填装数猜想与图的树连通度

The Nash-Williams-Tutte Theorem about spanning-tree packing problem is both a classical result and an important tool in structural graph theory. Steiner tree is a natural generalization of spanning tree and is popularly used in the physical design of VLSI circuits and network science. In 2003, Kriesell proposed a conjecture about Steiner tree packing problem, which can be seen as a generalization of the Nash-Williams-Tutte Theorem. Motivated by this conjecture, researchers have made important progress and obtained some technical methods in recent ten years. Also, West and Wu in 2012 proposed a new conjecture about S-connector. These conjectures are still open now. Tree-connectivity is a generalization of classical connectivity, which is another structural parameter of Steiner tree packing problem.. In this project, we are devoted to study Kriesell conjecture, West-Wu conjecture and tree-connectivity by classical tools in structural graph theory, extremal graph theory and algebra theory.

Nash-Williams-Tutte定理既是结构图论中的经典结果，又是生成树填装问题研究中的重要工具。作为生成树的自然推广，斯坦纳树在大规模集成电路设计和网络科学方面有着重要应用。Kriesell在2013年提出的关于斯坦纳树填装问题的猜想是Nash-Williams-Tutte定理的推广。在这个猜想的带动下，学者们在近10多年里取得了一些重要进展，同时也获得了一些方法和技巧。与此同时，West和Wu在2012年提出了关于S-连通子的猜想。目前，这两个猜想仍然没有解决。树连通度是经典连通度的推广，是斯坦纳树填装问题方面的另一个图参数。. 本项目运用经典结构图论和极值图论诸多研究工具和代数方法研究Kriesell猜想，West-Wu猜想和树连通度。

斯坦纳树在大规模集成电路设计和网络科学方面有着重要应用。本项目主要研究Kriesell 猜想、West-Wu 猜想和斯坦纳结构参数。前者与Kriesell猜想和Nash-Williams-Tutte定理紧密联系，是衡量网络安全性和可靠性的重要参数。后者在多处理器计算机网络方面和数学化学方面有着重要应用。. 本项目重要研究成果：1.获得了West-Wu 猜想的相关进展和结果。2.系统研究了斯坦纳维纳指标参数，并且研究了其在数学化学方面的应用。3. 利用本项目产生的新方法，对一般图的匹配排除集参数进行系统研究，为理论计算科学方面的特殊网络研究提供了理论和方法参考。.在斯坦纳结构参数方面，进行了广义连通度、悬挂树连通度和路连通度的算法复杂性分析，获得了Menger类型结果，研究了界问题、Nordhaus-Gaddum类型问题和极值问题，获得了一些研究新方法。. 受欧洲科学院院士Ivan Gutman教授邀请，主持人与其他国外专家一起撰写发表了数学化学学科的学术专著《Bounds in Chemical Graph Theory-Advances》，该专著是“Mathematical Chemistry Monographs”系列图书之一，系列图书旨在推动数学，特别是离散数学，应用于化学分子现象研究的发展。主持人毛亚平受邀专著题目为《Nordhaus-Gaddum Type Results in Chemical Graph Theory》(126页)，主要介绍了数学化学Nordhaus-Gaddum类型问题的研究背景和意义，总结了该方面几十年来的国际研究成果，同时提出了进一步研究的猜想和公开问题。. 依托本项目，出版专著1部；发表论文25篇，其中SCI论文23篇；举办国际学术会议6次；成员赴国外学习4次；项目主持人获得5项省部级以上奖励或荣誉称号，担任国际国内兼职8项；培养硕士研究生9名，培养博士研究生1名；3名项目研究生成员正在攻读博士研究生（荷兰屯特大学、西安电子科技大学、青海师范大学）。