Some Problems Related to Graph Connectivity

图图连通性（DMS-0245530）是图论中的基本概念。图论中的许多重要问题要么涉及到连通性，要么可以归结为具有一定连通性的图的问题。PI将研究图的收缩和图的分解，它们保持了一定程度的连通性。这将有潜在的应用于结构图论，包括图子。提出的研究的另一个方面是对具有一定连通性的图中的长循环（包括哈密顿循环）的研究。PI建议研究图中长周期的存在性（并确定寻找长周期的算法）。其中一些问题与几何结理论中关于结和连杆长度的问题有关。图连通性可以看作是一种网络可靠性，因此在计算机科学和组合优化中很重要。求图中的长循环是数学和计算机科学中的一个重要问题。它包括旅行推销员问题。该提案中的许多问题是长期存在的开放问题，引起了图论和计算机科学专家的广泛关注。这些问题的解决方案要么会导致新技术的发展，要么会为解决其他问题提供工具。该提案中的几个问题是由其他领域的问题引起的，包括网络可靠性和环状dna的长度（结的长度）。对这些问题的进一步理解将有助于理解图论与计算机科学以及图论与结论之间的相互作用。

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.