Graph 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.
