邻域并和二分图对集的可扩性

• 作 者: 苏本堂 逄世友
• 机 构: 山东农业大学基础部
• 出 处: 山东农业大学学报：自然科学版
• 发表日期: 1998年4期
• 关键词: 二分图 对集 领域并 bipartite graph matching neighborhood union

图Ｇ称为ｎ－可扩充的，如果对于Ｇ中任意ｎ条边的对集都可扩充为Ｇ的一个完美对美。本文研究了图的邻域并条件和二分图对集可扩性的关系，证明了下列结果：设Ｇ是一个具有二分划Ｘ和Ｙ的连通的二分图，│Ｘ│＝│Ｙ│，ｎ是整数且０≤ｎ≤│Ｘ│／２。如果δ（Ｇ）≥２ｎ＋１，且对于图Ｇ的任意两个不相邻的顶点ｕ，ｖ，有│Ｎ（ｕ）ＵＮ（ｖ）│≥│Ｘ│／２＋ｎ，则Ｇ是２ｎ－可扩充的。