二分图为k-消去图的2个条件

• 作 者: 杨宏晨 薛秀谦
• 机 构: 中国矿业大学理学院,徐州,221008
• 出 处: 东南大学学报(英文版)
• 发表日期: 2003年2期
• 关键词: 二分图 k-因子 k-消去图

图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)对所有SX成立.并由此给出二分图是k-消去图的一个邻集充分条件.