Matching preclusion for balanced hypercubes

作者：Lu Huazhong; Li Xianyue; Zhang Heping^*

来源：Theoretical Computer Science, 2012, 465: 10-20.

DOI：10.1016/j.tcs.2012.09.020

• Perfect matching
• Almost perfect matching
• Balanced hypercubes
• Matching preclusion set

Matching preclusion is a measure of robustness in the event of edge failure in interconnection networks. The matching preclusion number of a graph G is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching or an almost perfect matching, and the conditional matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph with no isolated vertices and without a perfect matching or an almost perfect matching. In this paper, we consider balanced hypercubes. We obtain that an n-dimension balanced hypercube BHn has the matching preclusion number 2n, and mainly prove that for the balanced hypercube BHn, each matching preclusion set of cardinality 2n is trivial, and the conditional matching preclusion number of balanced hypercube is 4n - 2 whenever n >= 2.

• 出版日期2012-12-21
• 单位兰州大学