关于k-消去二分图的一些结果  

Several Results for k-deleted Bipartite Graph

作　　者：杨宏晨[1] 

机构地区：[1]中国矿业大学理学院,江苏徐州221008

出　　处：《数学的实践与认识》2003年第11期131-135,共5页Mathematics in Practice and Theory

摘　　要：图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ 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. It is proved that a bipartite graph G=(X,Y) with ｜X｜=｜Y｜ is a k-deleted graph if and only if k|S|≤r 1+2r 2+…+k(r k+…+r Δ)-ε(S) for all SX. Then we give a sufficient degree condition for a bipartite graph to be k-deleted graph.

关 键 词：K-消去图 二分图 有限简单无向图 K-因子 

分 类 号：O157.5[理学—数学]