k-哈密尔顿连通与k-边哈密尔顿连通问题的研究

Hamilton problem is structure theory is extremely important and far-reaching significance in a project, the problems with the famous four-color, extreme value problem of many problems, such as there is a close relationship; In operational research, communications networks, social networks, computer science and coding theory and complexity theory has been widely used. A graph is called hamiltonian-connected if each pair vertice are joined by a hamiltonian-path. The hamiltonian-connected problem is also widely used. In this project, arounding hamiltonian-connected problem, we define k-edge-hamiltonian-connected, try to find some new sufficient conditions to judge the hamiltonian-connected graphs, k- hamiltonian-connected graphs and k-edge-hamiltonian-connected graphs, and explore the relationship between operations of graphs and hamiltonian-connected property.

哈密尔顿问题是结构图论中极其重要且意义深远的一个课题, 该问题与著名的四色问题, 极值问题等众多问题存在着密切的联系; 在运筹学、通讯网络、社交网络、计算机科学和编码理论、复杂性理论中有着广泛的应用。哈密尔顿连通图是指图中任意两点间都存在一条哈密尔顿路，这个问题同样有着广泛的应用。本项目围绕哈密尔顿连通问题，提出k-边哈密尔顿连通图的定义，主要针对哈密尔顿连通图，k-哈密尔顿连通图以及k-边哈密尔顿连通图的充分条件进行研究。此外，本项目进一步探究图的运算与哈密尔顿连通性的关系。

与哈密尔顿问题相关的圈的结构不仅是图论中的重要问题，同时是复杂网络研究的新方向。本项目围绕哈密尔顿性、最长圈问题、图的子图结构问题、网络可靠性以及超网络的性质等方面开展研究。本项目利用图的阶数、连通度以及独立数等条件，研究了非哈密尔顿图的最长圈的问题，确定一个最小的正整数使得图中存在一个最长圈经过所有度数至少为该整数的顶点；研究了无爪图中哈密尔顿充分性的条件，得到了利用导出圈的长度以及禁用子图条件来刻画无爪图的哈密尔顿性问题；讨论了图中含有至多有k个叶子结点的生成树问题，以及自相似网络中生成连通单圈子图数目问题；研究了二元拟阵的连通性问题以及简单正则拟阵的超欧拉性问题；研究了边失效下2-终端网络的可靠性的问题，解决了基于边失效下2-终端图族的一致最优存在性问题，同时研究了边以大（小）概率失效下的局部最优3-终端结构，刻画了在此条件下的若干局部最优3-终端结构；研究k均匀超网络的拓扑性质以及这类网络的点可控性与超边可控性。本项目的相关研究结果对理解发生在网络上的故障有重要的作用，对有效控制和预防网络故障的发生和蔓延奠定理论基础；此外，对优化网络结构、减轻和防止故障带来的危害有重要的参考价值和意义。