论文部分内容阅读
本文所涉及的图均为无向,有限,简单图.对边集M(∈)E(G),如果G的任意顶点至多与M中的一条边关联,则称M是G的匹配.称覆盖所有顶点的匹配为完美匹配.称图G是因子临界的,如果对G中任意的顶点u,G-u有一个完美匹配.称图G是独立集可削去因子临界的,如果对于G中任意与|V(G)|有相同奇偶性的独立集I,G-I有完美匹配.在匹配理论中,因子临界图是一类非常重要的图.因为由Gallai-Edmonds分解定理可知,研究图的最大匹配问题只需考虑有完美匹配的图,具有正赢量的图,因子临界图这三类图.当顶点数为奇数时,独立集可削去的因子临界图是一类特殊的因子临界图;当顶点数为偶数时,独立集可削去的因子临界图必然有完美匹配.因此,独立集可削去因子临界图的研究有重要意义.本文研究了独立集可削去的因子临界图的度条件,主要结果如下:
1.一般的独立集可削去的因子临界图的度条件定理2.2设G是一个有n个顶点的图,n≥3.如果对于G中任意不相邻的顶点u和v,有d(u)+d(v)≥2[2n-1/3]-1,那么G是独立集可削去的因子临界图,并且这是最好可能的.
推论2.3设G是一个有n个顶点的图,如果δ(G)≥[2n-1/3],那么G是独立集可削去的因子临界图.
2.无爪的独立集可削去的因子临界图的度条件图G称为无爪图,如果它不包含K1,3作为它的导出子图.引理3.1如果X是无爪图G的一个独立集,那么对任意的u∈V(G-X),|N(u)∩X|≤2.
定理3.3设G是一个有n个顶点的无爪图.如果对于G中任意不相邻的顶点u和v,我们有d(u)+d(v)≥2[n/2]+1,那么G是独立集可削去的因子临界图,并且这是最好可能的.
推论3.4设G是一个有n个顶点的无爪图.如果当n=4m时,δ≥[n/2]+1;否则,δ≥[n/2],那么G是独立集可削去的因子临界图.
定理3.5一个有n个顶点的[n/2]-正则无爪图是独立集可削去因子临界的.(n≠4,9)
定理3.6如果k和n是满足1≤[n/2]≤k≤n-1的正整数,那么任意的有n个顶点的k-正则无爪图G是独立集可削去因子临界的.