Graph Edge Decomposition and Graph Toughness

点击翻译按钮获取中文摘要

This project focuses on two central topics in graph theory: optimal edge partition into classes that avoid certain conflicts and the Hamiltonian cycle problem. Both problems have significant theoretical importance and have broad applications in fields such as combinatorial optimization and computer science. In general, finding an optimal edge partition of a certain kind is an NP-complete problem, so is determining the existence of a Hamiltonian cycle in a graph. Under the background of two famous conjectures from the two areas, this project dedicates to developing sufficient conditions that guarantee an optimal edge partition of a given type or the existence of a Hamiltonian cycle in a graph and developing novel techniques for both areas of research. The project also contains research problems that are suitable for students.Specifically, the PI will continue her investigation of two longstanding conjectures: the Overfull Conjecture of Chetwynd and Hilton from 1986 and the Toughness Conjecture of Chvatal from 1973. The PI and her collaborators have recently made significant contributions to both conjectures, but they remain open. For the Overfull Conjecture, extending some techniques that she and her collaborators developed recently, the PI will first investigate it for large graphs of order n and minimum degree arbitrarily close to half of n and explore algorithmic aspects. Then she will attack the conjecture for large graphs with only maximum degree constraints by applying and extending results obtained from the first step. She will also expand the techniques to attack the related Linear Arboricity Conjecture. For the Toughness Conjecture, the PI will gain more insights into it by working on a series of problems in finding spanning substructures under a given toughness condition. The problems include two challenging questions posed by Bauer, Broersma, and Schmeichel in a survey on graph toughness.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.