Disjoint Paths and Hamilton Cycles

不相交路径和哈密顿循环

• 批准号: 9531824
• 负责人: Xingxing Yu
• 金额: $ 6万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-08-01 至 2000-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9531824&HistoricalAwards=false
• 关键词: Disjoint; Paths; 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.

9531824 Yu这项研究是以前资助的NSF项目的延续。研究者已经解决了几个重要的问题，在图论中，一些在合作，包括1970年猜想的Grunbaum，1972年猜想的纳什-威廉姆斯，和1975年猜想的普卢默。亮点是解决的一个猜想的哈密尔顿汉密尔顿周期在局部平面三角形的表面和解决的一个猜想的罗伯逊和托马斯，都开辟了新的研究方向。研究者将把在解决上述问题中发展起来的寻找“Tutte路”和切割曲面的技术推广到解决面中图的汉密尔顿圈的其他一些重要问题。一个这样的例子是巴内特的一个古老猜想，它指出每个3连通的三次平面图，其中每个面最多由6条边包围，包含一个汉密尔顿圈。这个问题与化学中某些有机化合物的分子结构有关。另一个问题是Grunbaum（1970）和Nash-Williams（1973）的猜想，即每个4-连通环形图都包含一个汉密尔顿圈。研究者还将研究狄拉克（1964）关于K5-细分的猜想。Dirac猜想等价于猜想每个5-连通非平面图都含有一个K5-连通剖分。一种方法是刻画所有含有指定度为三个顶点的K4-剖分的4-连通图。这个问题与设计通信网络有关。最后，研究人员能够解决平面图的有根K4问题;他想扩展平面图的技术来攻击一般的有根K4问题。 这项研究是在组合数学的一般领域。组合数学的目标之一是找到有效的方法来研究如何安排对象的离散集合。 离散系统的行为对现代通信极为重要。 例如，大型网络的设计，如电话系统中的网络设计，以及计算机科学中的算法设计，都要处理离散的对象集，这就需要使用组合研究。