匹配覆盖图的相关研究
批准号：
12101203
项目类别：
青年科学基金项目（C类）
资助金额：
30.0 万元
负责人：
赵潇
依托单位：
学科分类：
图论及其应用
结题年份：
2024
批准年份：
2021
项目状态：
已结题
项目参与者：
赵潇
项目摘要
结项摘要
相似基金
相关文献
中文摘要
匹配覆盖图是匹配理论的主要研究专题之一.近年来,匹配覆盖图的研究工作已取得了丰富的成果,但仍有众多重要问题亟待解决.本项目主要研究匹配覆盖图的性质,旨在:第一,确定可以将一个耳分解序列中排序在后的双耳移到前面的条件,以及找到可以减少普通耳分解中的双耳数的方法;第二,研究IM-可扩图是否有性质更好的耳分解,比如是否存在一个耳分解序列,其耳朵的长度都不超过3;第三,给出立方体brick图上的b-invariant边数和brick图上的可删边数的下界.
英文摘要
Matching covered graph is one of the main research topics of matching theory.Although many results of matching covered graph were obtained in recent years,there are many important problems left to be resolved.This project mainly discusses the characters of matching covered graphs,it aims to: First,determine the conditions under which the ears that are sorted in the back of one ear decomposition can be moved to the front,and find a way to reduce the number of double ear of one ear decomposition.Second,study that whether IM-expandable graphs have better ear decomposition,such as whether there is an ear decomposition sequence whose ears are not more than 3.Third,give the number of b-invariant edges of the cube brick graph and the lower bound of the number of removable edges of bricks.
匹配问题和连通度问题是图论研究的两个重要内容，它们不仅对认识图的性质和结构起着重要的作用，而且在计算机科学、组合最优化和信息论等方面有着广泛地应用。本项目的研究将图的匹配和连通度相结合，一方面分析了图的结构连通度和匹配连通度的相关性质，另一方面研究了等匹配图和因子临界图的结构和性质，得到了一些有意义的成果，为研究图的连通性以及匹配相关问题提供了新的思路和工具。. 主要研究内容如下：. 第一，分析了图的匹配连通度。基于图的连通度的相关概念和结论，刻画了存在K_{1,1}-结构割的图，即匹配连通度有定义的图。证明了κ(G)/2≤κ_M (G)≤κ(G)，分别刻画了κ_M (G)=κ(G)和κ(G)/2=κ_M (G)的图。. 第二，研究了2-匹配连通图和3-匹配连通图的可添加边。如果在k-匹配连通图G中添加一条边e，G仍然是k-匹配连通的，则称e是可添加的。证明了2-匹配连通图G没有可添加边当且仅当G≌C_n和n≥4。并证明了任意满足δ(G)≥5的3-匹配连通图G都有可添加边。. 第三，探索了图的K_{1,2}-结构连通度。刻画了存在K_{1,2}-结构割的图类，进一步证明了κ(G)/3≤κ_{1,2}(G)≤κ(G)，并说明了该界是紧的。. 第四，刻画了度数大于等于6且α(G)≥3的偶正则等匹配图.如果图G的所有最大匹配都具有相同的大小，则称其为等匹配图。奇正则等匹配图、4-正则等匹配图和α(G)=2等匹配图均已被刻画。我们刻画了度数大于等于6且α(G)≥3的偶正则等匹配图。. 第五，研究了k-因子临界图的最小度问题。O. Favaron和M. Shi猜想每一个阶数为n的最小k-因子临界图的最小度数为k + 1，多位学者已经证明了该猜想对于k∈{n-2,n-4,n-6,n-8,n-10}时成立。我们证明了该猜想对于k=n-12亦成立。
国内基金
海外基金