Matching preclusion for vertex-transitive networks

In interconnection networks, matching preclusion is a measure of robustness in the event of link failure. Let GG be a graph of even order. The matching preclusion number mp(G)mp(G) is defined as the minimum number of edges whose deletion results in a graph without perfect matchings. Many interconnection networks are super matched, that is, their optimal matching preclusion sets are precisely those induced by a single vertex. In this paper, we obtain general results of vertex-transitive graphs including many known networks. A kk-regular connected vertex-transitive graph of even order has matching preclusion number kk and is super matched except for six classes of graphs. From this many results already known can be directly obtained and matching preclusion for some other networks, such as folded kk-cube graphs, Hamming graphs and halved kk-cube graphs, are derived.