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

The spanning tree of a connected graph is its minimal connected spanning subgraph. 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 that depend on degree and neighborhood union for 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路的图中路分解的最小数目问题.

项目研究基本按原计划执行.完全独立生成树的研究不仅在理论上值得研究,而且在网络数据广播、信息论、控制论、通信协议等领域中有重要作用.在完全独立生成树的存在性问题方面,我们得到了如下三个结果:(1)我们给出了含有k个完全独立生成树的极小图定义并刻画了存在k个完全独立生成树的所有极小图,这对我们寻找k个完全独立生成树的性质有很大帮助;(2)我们证明了完全t(t>=2)-部图K_{n_1,n_2,...,n_t}中存在⌊({n_{t-1}+n_{t-2}})/2⌋个完全独立生成树,该结果推广了已知结果;(3)在围长限制条件下,我们证明了不同构于圈C_n的任何2-连通图G的k次幂图中存在k个完全独立生成树. .另外,我们研究了图染色方面的χ-有界问题.图染色问题一直是图论中重要的研究范畴,在解决通讯系统的频率分配、任务调度、学校排课等问题中具有现实意义.Gyárfás和Sumner分别独立的提出了下面猜想(Gyárfás-Sumner猜想):令T为一任意的树(或森林),则存在函数f_T使得对每个不含T作为导出子图的图G来说,都有χ(G)<=f_T(ω(G)).Brause和M.Geiβer证明了如果图G是一个(P_5,dart)-free图,则χ(G)<=Θ(ω(G)^2/(log^ω(G))).设f(x)是一个函数使得f(3)=7,f(4)=21,f(5)=27,f(6)=32且若x>=7,则f(x)=(x^2+7x)/2.本项目中我们改进了Brause的结果并得到了:(4)如果G是一个(P_6,dart)-free图,则χ(G)<=f(ω(G));(5)若G是一个(P_6,C_5,dart)-free图且含有House,则χ(G)<=(ω(G)^2+3ω(G)+2)/2;进一步证明了若G是一个(P_6,C_5,dart)-free图且含有House,同时满足V(G)\V(H)中没有一个顶点与H的所有顶点都相连,则χ(G)<=4ω(G);(6)Cameron等人证明了若G是一个(P6,diamond)-free图,有χ(G)<=ω(G)+3.设g(x)是一个函数使得g(2)=4,若x>=3,则g(x)=ω(G)+3.我们改进Cameron的结果得到了：若G是一个(P2∪P4,diamond)-free图,则χ(G)<=g(ω(G)).