基于图与超图的匹配中的若干问题的研究

项目名称： 基于图与超图的匹配中的若干问题的研究

项目编号： No.11471257

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 鲁红亮

作者单位： 西安交通大学

项目金额： 60万元

中文摘要： 图的匹配及图的度约束因子理论最早由Tutte展开研究，并被沃尔夫奖得主Lovasz等发展，一直是图论中的热门和重点研究方向之一。近年来，超图的匹配问题受到包括美国与欧洲双科院士R?dl教授等人的关注。Rodl教授在2010年关于超图综述中着重介绍了超图的完美匹配存在性的度条件。 本项目旨在研究图的不连续的度约束因子问题及超图的匹配中的一些问题。首先，项目拟研究图的度约束因子的结构理论，采用H-因子结构理论研究度约束因子理论中的一些公开问题；其次项目申请人拟进行超图的匹配及超图的因子问题的研究，主要研究k-超图及k-分k-超图的各种度条件与其匹配的存在性之间的关系及k-超图的限制完美匹配与其最小度之间的关系，拟依据超图的最小度给出匹配及限制匹配存在性的一些充分条件。 本项目的研究成果将有助于研究者更好的理解图的间隔至多为一的度约束因子的结构理论及超图的匹配问题，能增强国内在该方向上的研究。

中文关键词： 匹配；H-因子；超图；可扩性

英文摘要： Matching theory and the theory of degree constrained factors in graph theory, which was first studied by Tutte, and then developed by Lovasz etc. who was awarded the Wolf Prize, is always one of the main research fields in graph theory. Recently, matchings in hypergraphs has attracted much attention of scholars including Professor R?dl, a member of both the US National Academy of Sciences and the European Academy of Sciences. R?dl emphatically introduced a degree condition for the existence of perfect matchings in hypergraphs in a survey on hypergraphs in 2010. The goal of this project is to investigate non-consecutive degree constrained factor problems in graph theory and some problems in matchings of hypergraphs. First, we will study on the structure theory of degree constrained factors of graphs. By applying H-factor structure theory we will try to tackle some open problems in the theory of degree constrained factors. Second, we will study on the matching and factor problems of hypergraphs. We will mainly focus on exploring the relation between various degree conditions of k-uniform hypergraphs and k-partite k-uniform hypergraphs and the existence of their matchings, as well as the relation between the existence of restricted perfect matchings of a k-uniform hypergraphand its mimimum degree. Meanwhile, some sufficient conditions for the existence of matchings and restricted perfect matchings of a hypergraph will be presented according to its minimum degree. The results of this research will enhance the understanding of the structure theory of non-consecutive degree constrained factors of graphs and matching problems in hypergraphs, and boost the domestic research on these topics.

英文关键词： matching;H-factor;hypergraph;extendability