论文部分内容阅读
匹配理论是图论中一个重要的基础分支,它不仅对认识图的结构有重要作用,而且也广泛的应用到组合优化,理论化学等研究领域。匹配可扩理论是匹配理论中热门的研究方向,已产生了许多有价值的结论,特别是引入了k-可扩图、n-因子临界图、(n,k,d)-图、k-圈共振图等一系列图类,这些概念的引入对进一步揭示图的结构有重要的贡献。本文主要研究了1-可扩图中可去耳朵数的下界,图的分数匹配可扩性,奇图(阶为奇数)的匹配可扩性以及如何用最少的完美匹配覆盖图中所有边等问题。
设G是一个图。如果删除G中任意n个点后所得的余图有k-匹配,并且任意的k-匹配都可以扩充为该余图的一个亏d-匹配,那么称G是一个(n,k,d)-图[1]。显然这一概念是k-可扩图和n-因子临界图的推广。k-可扩图对应的是(0,k,0)-图,n-因子临界图对应的是(n,0,0)-图。本文我们也称(0,k,1)-图是几乎k-可扩图。下面是本文的主要结果:
1.改进了Carvalho,Lucchesi与Murty [2]给出的1-可扩图中可去耳朵数的下界,证明了任意一个1-可扩图G至少有χ(G)个边不交的可去耳朵,其中χ(G)表示图G的边色数;并得到了1-可扩图中可去边的一些性质。
2.设G是一个1-可扩图,χe(G)表示覆盖G中所有边所需最少完美匹配的数目,称为图G的excessive指数。我们给出了χe(G)的一个紧的上界;对任意正整数k≥3,构造了一个图G使得△(G)=3但χe(G)=k;进而研究了乘积图G×H的excessive指数χe(G×H)。
3. 改进了已有的(n,k,d)-图的刻画;给出了几乎k-可扩图和几乎k-可扩二部图的刻画;研究了几乎k-可扩图与n-因子临界图之间的关系,去边和加边对几乎k-可扩图的影响以及平面奇图的匹配可扩性。
4.给出了分数尼一可扩图的两个充分条件和极小分数k-可扩图的刻画;证明了分数后k-可扩二部图与k-可扩二部图是等价的;并研究了分数k-可扩图与n-因子临界图之间的关系。