Portal de Periódicos da CAPES

Matching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper‐stars

2011; Wiley; Volume: 59; Issue: 4 Linguagem: Inglês

10.1002/net.20441

1097-0037

Eddie Cheng, Philip Hu, Roger Jia, László Lipták,

Advancements in Battery Materials

Abstract The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. It is natural to look for obstruction sets beyond those induced by a single vertex. The conditional matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph with no isolated vertices that has no perfect matchings. In this companion paper of Cheng et al. (Networks (NET 1554)), we find these numbers for a number of popular interconnection networks including hypercubes, star graphs, Cayley graphs generated by transposition trees and hyper‐stars. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011