Matching preclusion for balanced hypercubes
Matching preclusion for balanced hypercubes
复制标题
平衡超立方体的匹配排除
DOI：
10.1016/j.tcs.2012.09.020
复制
发表时间：
2012-12
影响因子：
1.1
通讯作者：
Zhang, Heping
中科院分区：
文献类型：
--
作者：
Lu, Huazhong;Li, Xianyue;Zhang, Heping
匹配排除是在互连网络中发生边故障时的稳健性的衡量标准。图G的匹配排除数是其删除使得结果图没有完全匹配或几乎完全匹配的边的最小数目，而G的条件匹配排除数是其删除使结果图没有孤立顶点且没有完全匹配或几乎完全匹配的边的最小数目。在本文中，我们考虑平衡超立方体。得到了n维平衡超立方体BHn的匹配排除数为2n，并主要证明了对于n维平衡超立方体BHn，基数为2n的每个匹配排除集都是平凡的，且当n−2时，平衡超立方体的条件匹配排除数为4N≥2.
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 BHnhas 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.
登录
查看更多内容
DOI：
10.1016/s0020-0255(96)00270-8
发表时间：
1997-07
期刊：
Inf. Sci.
影响因子：
--
作者：
Ke Huang;Jie Wu
通讯作者：
Ke Huang;Jie Wu
影响因子：
2.1
作者：
E. Cheng;Philip Hu;Roger Jia;László Lipták
通讯作者：
E. Cheng;Philip Hu;Roger Jia;László Lipták
DOI：
10.1016/j.dam.2012.03.014
发表时间：
2012-08
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
E. Cheng;László Lipták
通讯作者：
E. Cheng;László Lipták
DOI：
10.1016/j.tcs.2011.08.008
发表时间：
2011-10
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Jung-Heum Park;I. Ihm
通讯作者：
Jung-Heum Park;I. Ihm
影响因子：
2.1
作者：
E. Cheng;László Lipták
通讯作者：
E. Cheng;László Lipták