Disjoint Paths and Hamilton Cycles

点击翻译按钮获取中文摘要

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.