Matching preclusion for vertex-transitive networks.

In interconnection networks, matching preclusion is a measure of robustness in the event of link failure. Let G be a graph of even order. The matching preclusion number m p ( 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 k -regular connected vertex-transitive graph of even order has matching preclusion number k 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 k -cube graphs, Hamming graphs and halved k -cube graphs, are derived. [ABSTRACT FROM AUTHOR]