关于图的路因子和圈的研究

In this project, we focus on studying some problems of path factors, Hamilton cycles and the relations between the k-dominating cycles and the longest cycles in graphs. In the path factor problem, we intend to solove a problem posed by Kaneko and Kano, that is, find a criterio for a graph that has a {P4, P5, P6, P7}-factor; in the hamiltonian problem, we would find a necessary and sufficient condition for a graph having a Hamilton cycle. We would prove that for any k-connected graphs with at least 3 vertices, if the degree sum of any k+1 independent vertices is at least n+(k-1)(m+1), where m is the independent number of the graph, then the graph has a Hamilton cycle; in the last problem, we would focus on finding the relation between the k-dominating cycles and the longest cycles in graphs. These problems are closely related to networks. We could use the theoretical results established here to solove some real problems related to networks in practical situations.

本项目主要研究图的路因子和圈以及相关应用的几个重要问题：研究图的路因子问题，力求解决Kaneko 和Kano提出的与图的路因子有关的问题，即找出衡量一个图有一个{P4，P5，P6，P7}-因子的尺度；研究图的哈密尔顿圈的问题，力求解决与图的哈密尔顿圈有关的问题：对每个顶点数至少是3 的k-连通图，如果任意k+1个独立点的度和都至少是n+(k-1)(m-1)（其中m 是图中独立集的大小），则这个图有一个哈密尔顿圈；研究图的k-控制圈与最长圈的关系。这些问题的解决将对网络理论的发展有较大的促进作用，进而做到理论与实践相结合，解决与网络应用有关的实际问题。

图的路和圈是图论研究的基本方向，其研究方式也渗透到了图论的各个领域包括：图的不交森林，图的染色以及优化系统里的n中取r问题等等。本项目主要研究了与图的路和圈相关的几个重要问题。这些问题的解决将对网络理论的发展有较大的促进作用，通过理论与实践相结合，进一步解决与网络应用有关的实际问题。我们首先在可平面图类中研究了领域和可区分的边染色，得到了如下结果：对任意一个不含K4图子式的图，如果最大度Δ(G)≥5，那么它的领域和可区分的边色数最多是Δ(G)+1。进一步，我们证明了该上界Δ(G)+1是紧的。其次，我们研究了领域和可区分的全染色。在这方面，Pilsniak和Wozniak曾提出过一个猜想，他们认为只需要Δ(G)+ 3种颜色就可以保证领域和可区分的全染色存在。我们证明了该猜想对Δ(G)=10的所有可平面图都是成立的。而且, 对Δ(G)≥11的可平面图, Δ(G)+2种颜色就可以保证这样一个正常的全染色，并且该上界是紧的。此外，我们还将处理路和圈的基本方法应用到了网络可靠性理论中。在现实网络系统中，系统及其元件可能是多状态的，我们研究了如何将k个冗余元件热分配到多状态的n中取r系统中，最优策略是将更多的元件分配到随机意义下较弱的位置。