Matching preclusion for some interconnection networks

Abstract

Abstract The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost‐perfect matchings. In this paper, we find this number for various classes of interconnection networks and classify all the optimal solutions. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 173–180 2007