Matching preclusion for cube-connected cycles
Matching preclusion for cube-connected cycles
复制标题
立方体连接循环的匹配排除
DOI：
10.1016/j.dam.2015.04.001
复制
发表时间：
2015
影响因子：
1.1
通讯作者：
Yao Haiyuan
中科院分区：
文献类型：
--
作者：
Li Qiuli;Shiu Wai Chee;Yao Haiyuan
匹配排除是互连网络中边缘失效时鲁棒性的度量。偶数阶图G的匹配排除数是删除使图G不存在完美匹配的最小边数，G的条件匹配排除数是删除使图G不存在孤立点和完美匹配的最小边数.本文研究了立方连通圈网络C C Cn的匹配排除问题。利用点传递图的超边连通度、C C Cn（n= 3，4，5）的超循环边连通度、Hall定理和加强的Tutte定理，得到了C C Cn的匹配排除数和条件匹配排除数，并对相应的最优匹配排除集进行了分类.
Matching preclusion is a measure of robustness in the event of edge failure in interconnection networks. The matching preclusion number of a graph G with even order is the minimum number of edges whose deletion results in a graph without perfect matchings 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 perfect matchings. We consider matching preclusion of cube-connected cycles network C C C n. By using the super-edge-connectivity of vertex-transitive graphs, the super cyclically edge-connectivity of C C C n for n= 3, 4 and 5, Hall’s Theorem and the strengthened Tutte’s Theorem, we obtain the matching preclusion number and the conditional matching preclusion number of C C C n and classify respective optimal matching preclusion sets.