Some Problems Related to Graph Connectivity

与图连通性相关的一些问题

• 批准号: 0245530
• 负责人: Xingxing Yu
• 金额: $ 10.5万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-01 至 2006-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0245530&HistoricalAwards=false
• 关键词: Some; Problems; Related; Graph; Connectivity

Abstract for the Award DMS-0245530 of YuGraph connectivity is a fundamental concept in graph theory. Many important problems in graph theory either involve connectivity or can be reduced to problems about graphs with a certain connectivity. The PI will study graph contractions and graph decompositions which preserve a certain degree of connectivity. This will have potential applications to structural graph theory, including graph minors. Another aspect of the proposed research is the study of long cycles (including Hamiltonian cycles) in graphs with a certain connectivity. The PI proposes to study the existence of (and determine algorithms for finding) long cycles in graphs. Some of those problems are related to a problem in geometric knot theory about the lengths of knots and links.Graph connectivity may be viewed as a type of network reliability, and hence, is important in computer science and combinatorial optimization. Finding long cycles in graphs is an important problem in mathematics and computer science; it includes the Traveling Salesperson Problem. Many problems in this proposal are long-standing open problems, which have attracted much attention from experts in graph theory and computer science. Solutions to these problems will either lead to the development of new techniques or provide tools for solving other problems. Several problems in this proposal were motivated by problems in other areas, including network reliability and lengths of circular DNAs (lengths of knots). Further understanding of these problems will be useful for understanding the interplay between graph theory and computer science and between graph theory and knot theory.

摘要奖DMS-0245530 YuGraph连通性是图论中的一个基本概念。图论中的许多重要问题要么涉及连通性，要么可以归结为关于具有某种连通性的图的问题。PI将研究 图的收缩和图的分解，保持一定程度的连通性。这将有潜在的应用结构图论，包括图未成年人。 另一方面，研究具有一定连通度的图中的长圈（包括Hamilton圈）。 PI建议研究图中长圈的存在性（并确定查找算法）。这些问题中的一些与几何纽结理论中关于纽结和链环长度的问题有关。图连通性可以被看作是网络可靠性的一种类型，因此在计算机科学和组合优化中很重要。寻找图中的长圈是数学和计算机科学中的一个重要问题，它包括旅行商问题。该方案中的许多问题都是长期存在的开放问题，引起了图论和计算机科学专家的广泛关注。这些问题的解决方案将导致新技术的发展或提供解决其他问题的工具。该提案中的几个问题是由其他领域的问题引起的，包括网络可靠性和圆形DNA的长度（结的长度）。 对这些问题的进一步理解将有助于理解图论与计算机科学之间以及图论与纽结理论之间的相互作用。