Matching extensions in graphs and hypergraphs: structures, algorithms and characterizations

图和超图的匹配扩展：结构、算法和表征

• 批准号: RGPIN-2019-06429
• 负责人: Yu, Qinglin
• 金额: $ 1.09万
• 依托单位: Thompson Rivers University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=738905
• 关键词: Matching; extensions; graphs; hypergraphs; structures

Matching extensions in graphs and hypergraphs: structures, algorithms and characterizations Graph Theory is a traditional branch of mathematics, but it has recently been re-energized with its increase applications to Physics, Biology and Operations Research, in particular to Computing Science and communication networks. Often graphs are used as a working frame for various scientific investigations. In particular, Computing Science has provided many interesting problems for Graph Theory to grow. More recently, Graph Theory has become a useful instrument for the study of gene sequences, environment sustainability, management science and logic designing. The proposed program is to expand our knowledge on graph factors, subgraph extension and its connection to other combinatorial topics. The objectives are to acquire knowledge, both for research and HQP training in three ways: 1) To understand the structures of subgraph extension graphs (i.e., (Y, H)-extendable graphs) by developing a decomposition procedure for the purpose of general recursive arguments. Such a decomposition will be vital for the design of efficient algorithms to recognize and to construct the family of such graphs. This work involves generalizing the existing techniques and methods, and creating new analysis tools for the general framework and abstract models. 2) The research will deliver a more consistent and universal framework for the potential applications of subgraph extension to other combinatorial problems and other mathematical branches. The concept, (Y, H)-extendable graphs, is a well-defined framework, which not only consolidates many well-known concepts (e.g., factor-critical graph, bicritical graphs and defect-d matching) together but also maintains the basic properties of its sub-classes. This enables us to simplify many of the previous proofs and establish closer connections to other graph theory problems. 3) In our proposal, we have stated many closely related and well-defined problems. These problems have different levels of difficulties, from conjectures and open problems, to generalization of known results and construction of specified classes of graphs; we also carefully select and blend the problems in this proposal by considering our short-term and long-term objectives. The problems proposed will fulfill my vision of understanding subgraph extension and also provide opportunities for the involvement of undergraduate and graduate students to engage in creation, exploration and experience of rigorous research.

图论是数学的一个传统的分支，但最近随着它在物理学、生物学和运筹学，特别是在计算科学和通信网络中的应用的增加而重新活跃起来。图表经常被用作各种科学研究的工作框架。特别是，计算科学为图论的发展提供了许多有趣的问题。最近，图论已成为研究基因序列、环境可持续性、管理科学和逻辑设计的有用工具。 建议的计划是扩大我们的知识，图的因素，子图的扩展和连接到其他组合的主题。目标是以三种方式获得知识，用于研究和HQP培训：1）理解子图扩展图的结构（即，（Y，H）-可扩展图）的一般递归参数的目的，通过开发一个分解过程。这种分解对于设计识别和构造此类图族的高效算法至关重要。这项工作涉及到对现有技术和方法的推广，以及为通用框架和抽象模型创建新的分析工具。 2)该研究将为子图扩展到其他组合问题和其他数学分支的潜在应用提供一个更一致和通用的框架。概念（Y，H）-可扩展图是一个定义良好的框架，它不仅巩固了许多众所周知的概念（例如，因子临界图、双临界图和缺陷-D匹配）在一起，而且还保持了它的子类的基本性质。这使我们能够简化许多以前的证明，并建立更密切的联系，以其他图论问题。 3)在我们的建议中，我们提出了许多密切相关和明确界定的问题。这些问题有不同程度的困难，从结构和开放的问题，推广已知的结果和特定类别的图的建设，我们也仔细选择和混合的问题，在这个建议，考虑我们的短期和长期目标。所提出的问题将实现我理解子图扩展的愿景，也为本科生和研究生参与创造，探索和严格的研究经验提供了机会。