CAJ | 학술논문

图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-消去图的一个邻集充分条件.
도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-소거도적일개린집충분조건.
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≤r1+2r2+...+k(rk+...+rΔ)-ε(S) for all SX. Using this result we give a sufficient neighborhood condition for a bipartite to be a k-deleted graph.