Conditional matching preclusion sets (Q1006754)

The matching preclusion concept was introduced as a measure of robustness in interconnection networks. A desired property is that the only minimum way to preclude a perfect (respectively, almost-perfect) matching is to delete all edges incident to a single vertex (respectively, all edges incident to two vertices). A natural question is to see how several are these obstructions. In this paper, the authors answer such a question via a conditional version of matching preclusion sets. Since the most popular and fundamental interconnection network is the hypercube, they solved this problem for it and other basic classes of graphs in this paper.