摘要
A k-regular spanning subgraph of graph G is called a k-factor of G. Graph G is called a k-deleted graph if G-e has a k-factor for each edge e. A graph G=(X,Y) with bipartition (X,Y) is called a bipartite graph if every edge of G has one endpoint in X and the other in Y.It is proved that a bipartite graph G=(X,Y) with X=Y is a k-deleted graph if and only if kS≤r 1+2r 2+...+k(r k+...+r Δ)-ε(S) for all SX. Using this result we give a sufficient neighborhood condition for a bipartite to be a k-deleted graph.
图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 消去图的一个邻集充分条件 .
