关于完全独立生成树及树嵌入的研究

树是图中很重要的结构,每个连通图都含有生成树.生成树的研究不仅在理论上有意义而且在实际应用中有重要作用.本项目主要研究以下三个问题:(1)找出哈密尔顿图中存在两个完全独立生成树的条件;(2)满足一定的连通度条件下要给出存在k个完全独立生成树的条件;(3)Erdos-Sos猜想为:若G是n个顶点的图且e(G)>n(k-1)/2,则G含每个k条边的树.本项目围绕Erdos-Sos猜想争取得到部分结果.

A trees is a very important structure in graphs and each connected graph contains a spanning trees. The study of independent spanning trees has theoretical significance and plays an important role in practical applications. In this project, we focus on the following three problems:(1)Find a condition for two completely independent spanning trees in Hamiltonian graphs;(2)Determine a condition which ensure that there exist k completely independent spanning trees under some connectivity condition;(3)Erdos-Sos conjecture: If G is a graph on n vertices with e(G)>n(k-1)/2,then G contains every tree of k edges. In the project, we try to obtain partially results aroud the conjecture.