摘要
设G是一个具有二分类(X_1,X_2)的简单偶图,|X_1|=|X_2|=n,如果对于给定的c>0,|M(S)|≥(1+c)|S|对任意满足|S|≤n/2的S(?)X_i(i=1,2)都成立,其中N(S)是S的邻集,则称G是(n,c)-扩张图.给出了(n,c)-扩张图的k-匹配数与完美匹配数之比的顺从界.
Given c 〉 0, an （n, c）-expander is a simple bigraph with bipartition （X1,X2） and ｜X1｜ =｜X2｜= n, such that ｜N（S）｜ ≥ （1＋c）｜S｜ for every S Xi （i = 1, 2） with ｜S｜≤n/ 2, where N（S） is the neighbour set of S. In this paper, amenable bounds on the ratios of the number of k-matchings to the number of perfect matchings of an （n, c）-expander are obtained.
出处
《数学的实践与认识》
CSCD
北大核心
2010年第3期151-154,共4页
Mathematics in Practice and Theory
基金
国家自然科学基金(90818004
60673119)
关键词
二分图
匹配
交错路
bigraph
matching
alternating path
