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

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

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.