步长为1和4的循环图的k-偶匹配可扩性

摘要

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否含有基数为k的偶匹配是NP-困难问题,该文主要刻画了循环图C2n(1,4)的k-偶匹配可扩性.%G is said to be bipartite matching-extendable,if every bipartite matching M of is included in a perfect matching of G . The problem determining whether there is a bipartite matching of cardinality k in a graph G is NP-complete. This paper shows that the k-bipartite matching extendability of circulant graphs C2n(1,4) .