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

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.

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

树是图中很重要的结构,每个连通图都含有生成树.生成树的研究不仅在理论上有意义而且在实际应用中有重要作用.本项目主要研究了以下三个问题:(1)找出了哈密尔顿图中存在两个完全独立生成树的条件;(2)证明了任何k-连通图的k次幂图含有k个完全独立生成树;(3)围绕Erdős-Sós猜想,我们得到了部分结果:设G是n个顶点的无三角形图且e(G)>\frac{k-1}{2}n,T是k条边的树,若T满足下列条件之一,则T可嵌入到G:(i)T中存在一个顶点使得度至少\frac{k}{2};(ii)T由两个树分支T_{1},T_{2}组成且V(T_{1})\capV(T_{2})=v_{i},这里T_{1}=v_{0}\cdotsv_{s}是s(s\leqk)条边的路,T_{2}是根为v_{i}的k-s条边的树使得d_{T_{2}}(v_{i})\geq\frac{k-s}{2},其中i\in\{0,\dots,s\}.事实上,这里第二类树是第一类树的推广;(4)图的控制理论中确定了一些图类的符号罗马控制数.