图G的一个k正则支撑子图称为G的k因子.若对G的任一边e,图G总存在一个k因子不含e,则称G是k消去图.若图G存在一个划分(X,Y)使得G的每条边的端点分别在X和Y中,则称G=(X,Y)为二分图.证明了二分图G=(X,Y)且X=Y是k消去图的充分必要条件是kS≤r1+2r2+…+k(rk+…+rΔ)-ε(S)对所有SX成立.并由此给出二分图是k消去图的一个邻集充分条件.
东南大学学报:英文版
2003年2期