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.

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