Disjoint Paths and Hamilton Cycles

9531824余这项调查是先前资助的国家科学基金会项目的延续。这位研究人员已经解决了图论中的几个重要问题，其中一些是合作的，包括1970年Grunbaum的猜想，1972年的Nash-Williams猜想和1975年的Plummer猜想。其中的亮点是关于曲面的局部平面三角剖分中的Hamilton圈的Thomassen猜想的解，以及Robertson和Thomas猜想的解；这两个猜想都为研究开辟了新的方向。作者将把在解决上述问题中发展起来的寻找“Tutte路”和切割曲面的技术加以推广，以解决曲面图中关于哈密尔顿圈的其他一些重要问题。一个这样的例子是Barnette的一个古老的猜想，它指出每个面至多由6条边限定的3-连通三次平面图包含一个哈密尔顿圈。这个问题与化学中某些有机化合物的分子结构有关。另一个问题是Grunbaum(1970)和Nash-Williams(1973)的猜想，即每个4-连通的环形图都包含一个哈密尔顿圈。这位研究者还将研究狄拉克(1964)关于K5-细分的一个猜想。Dirac猜想等价于猜想：每个5-连通非平面图都包含一个K5-连通剖分。一种方法是刻划所有4-连通图，其中包含一个指定度为3个顶点的K4-细分。这个问题与通信网络的设计有关。最后，研究人员能够解决平面图的有根K4问题；他希望扩展用于平面图的技术来攻击一般的有根K4问题。这项研究属于组合学的一般领域。组合学的目标之一是找到有效的方法来研究离散的对象集合如何排列。离散系统的行为对于现代通信来说是极其重要的。例如，大型网络的设计，如那些发生在电话系统中的网络，以及计算机科学中的算法设计，都涉及离散的对象集，这利用了组合研究。

9531824 Yu This investigation is a continuation of previously funded NSF projects. The investigator has solved several important problems in graph theory, some in collaboration, including a 1970 conjecture of Grunbaum, a 1972 conjecture of Nash-Williams, and a 1975 conjecture of Plummer. The highlights are the solution of a conjecture of Thomassen about Hamilton cycles in locally planar triangulations of surfaces and the solution of a conjecture of Robertson and Thomas; both have opened up new directions for research. The investigator will extend the techniques of finding "Tutte paths" and cutting surfaces developed in solving the above mentioned problems to attack some other important problems about Hamilton cycles in graphs in surfaces. One such example is an old conjecture of Barnette, which states that every 3-connected cubic plane graph in which each face is bounded by at most 6 edges contains a Hamilton cycle. This problem is related to molecular structures of certain organic compounds in Chemistry. Another problem is the conjecture of Grunbaum (1970) and Nash-Williams (1973) that every 4-connected toroidal graph contains a Hamilton cycle. The investigator will also work on a conjecture of Dirac (1964) about K5-subdivisions. Dirac's conjecture is equivalent to the conjecture that every 5-connected non-planar graph contains a K5-connected subdivision. One approach is to characterize all 4-connected graphs containing a K4-subdivision with prescribed degree three vertices. This problem is related to designing communication networks. Finally, the investigator was able to solve the rooted K4 problem for planar graphs; he would like to extend the techniques used for planar graphs to attack the general rooted K4 problem. This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.