| 循环图C_(2n)(1,4)的偶匹配可扩性 |
| |
| 作者单位： | ;1.平顶山学院数学与统计学院 |
| |
| 摘 要： | 称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否是偶匹配可扩的是co-NP-完全问题,根据图的k-偶匹配可扩性完全刻画了循环图C2n(1,4)的偶匹配可扩性.
|
| 关 键 词： | 完美匹配 偶匹配可扩 k-偶匹配可扩 循环图 |
Bipartite Matching Extendability of Circulant Graph C_(2n)(1,4) |
| |
| Affiliation: | ,School of Mathematics and Statistics,Pingdingshan University |
| |
| Abstract: | G is said to be bipartite matching-extendable,if every bipartite matching M is included in a perfect matching of G. The problem determining whether a graph G is bipartite matching-extendable is co-NP-complete. In this paper we show the bipartite matching extendability of circulant graph C_(2n)(1,4),according to k-bipartite matching extendability of graphs. |
| |
| Keywords: | perfect matching bipartite matching k-bipartite matching extendable circulant graph |
|
|
