完全独立生成树的存在性和路分解问题的研究

A spanning tree of a connected graph is a minimal connected spanning subgraph. The study of independent spanning trees has theoretical significance and plays an important role in many practical applications. In this project, we focus on the following three problems:(1) find degree sum and neighborhood union conditions for the existence of two completely independent spanning trees in Hamiltonian graphs;(2) give the existence conditions of k completely independent spanning trees under the Ore type condition;(3) consider the problem of the minimum number of path decompositions in a graph with Hamilton paths.

连通图的生成树是它的极小连通生成子图.生成树的研究不仅在理论上有意义而且在实际应用中有重要作用.本项目主要研究以下三个问题:(1)找出存在两个完全独立生成树的依赖于度和而及邻域并的哈密尔顿条件;(2)给出Ore类型条件下的k个完全独立生成树的存在性条件;(3)考虑含有Hamilton路的图中路分解的最小数目问题.

我们研究了两个完全独立生成树的依赖于度和邻域并的条件， 得到了一些有意义的新结果。.给出了含有 k个完全独立生成树的极小图定义并刻画了存在 k个完全独立生成树的所有极小图，部分回答了Benoit Darties 提出公开问题。得到了完全t 部图中存在多个完全独立生成树的结果，该结果推广了一些已有的结论，我们还给出了(P6, dart)-free图类色数的二次多项式界定函数。