Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
395845 | Information Sciences | 2009 | 10 Pages |
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. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. In this paper, we look for obstruction sets beyond these sets. We introduce the conditional matching preclusion number of a graph. It is the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. We find this number and classify all optimal sets for several basic classes of graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Eddie Cheng, Linda Lesniak, Marc J. Lipman, László Lipták,