Graph Edge Decomposition and Graph Toughness

图边分解和图韧性

基本信息

批准号：
2153938
负责人：
Songling Shan
金额：
$ 12.18万
依托单位：
Board of Trustees of Illinois State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-08-01 至 2023-11-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2153938&HistoricalAwards=false
关键词：
Graph Edge Decomposition 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.

该项目重点介绍了图理论中的两个核心主题：最佳边缘分区分为避免某些冲突和汉密尔顿周期问题的类别。这两个问题具有重要的理论意义，并且在组合优化和计算机科学等领域中具有广泛的应用。通常，找到某种形式的最佳边缘分区是一个NP完整的问题，因此确定图表中哈密顿循环的存在。在这两个领域的两个著名猜想的背景下，该项目致力于开发足够的条件，以保证给定类型的最佳边缘分区或在图中的哈密顿周期存在，并为这两个研究领域开发了新颖的技术。该项目还包含适合学生的研究问题。特别是，PI将继续调查两个长期的猜想：Chetwynd和Hilton从1986年开始的过失猜想，以及1973年的Chvatal的韧性。PI和她的合作者最近为这两个猜想做出了重大贡献，但他们仍然开放。对于Overfull的猜想，扩展了她和她的合作者最近开发的一些技术，PI将首先对其进行调查，以确保n和最低程度的大图和最低程度的最低程度，并任意接近N的一半并探索算法方面。然后，她将通过应用和扩展从第一步获得的结果来攻击只有最大程度约束的大图的猜想。她还将扩展技术以攻击相关的线性树木猜想。对于韧性的猜想，PI将通过解决在给定韧性条件下找到跨越子结构的一系列问题来获得更多的见解。这些问题包括鲍尔（Bauer），布罗斯玛（Broersma）和施密切尔（Schmeichel）在一项关于图形韧性的调查中提出的两个具有挑战性的问题。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子和更广泛影响的评估评估标准来通过评估来支持的。