Generalized Matching Preclusion in Bipartite Graphs

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 such sets are precisely sets of edges incident to a single vertex. The conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond these, and it is defined as the minimum number of edges whose deletion results in a graph with neither isolated vertices nor perfect matchings. In this paper we generalize this concept to get a hierarchy of stronger matching preclusion properties in bipartite graphs, and completely characterize such properties of complete bipartite graphs and hypercubes.

Keywords

• Interconnection network
• perfect matching
• bipartite graph