Matching Preclusion Number in Cartesian Product of Graphs and its Application to Interconnection Networks.
Aline Ribeiro de Almeida, Fábio Protti, Lilian Markenzon · Ars Combinatoria · 2013
The matching preclusion number of a graph G, mp(G), is the minimum number of edges whose deletion leaves a resulting graph that has neither perfect matchings nor almost perfect matchings. Besides its theoretical linkage with conditional connectivity and extremal graph theory, the matching preclusion number is a measure of robustness in interconnection networks. In this paper we develop general properties related to matchings in the Cartesian product of graphs which allow us, in a simple manner, to establish the matching preclusion number for some interconnection (product) networks, namely: hyper Petersen, folded Petersen, folded Petersen cube, hyperstar, star-cube and hypercube. We also conclude that the Cartesian product of graphs operation inherits the matching preclusion number optimality from factor graphs of even order, which reinforces the Cartesian product as a good network-synthesizing operator.