![Sample our Computer Science journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5928/TOC-Subject-Sample-2021-Computer-Science.jpg"})
Abstract
The matching preclusion number of a graph is the minimum number of edges the deletion of which 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. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges the deletion of which results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this article, we find this number and classify all optimal sets for the alternating group graphs, one of the most popular interconnection networks, and their companion graphs, the split-stars. Moreover, some general results on the conditional matching preclusion problems are also presented.
Acknowledgements
Research partially supported by the NSF-REU Grant DMS 0649099. We would like to thank the three anonymous referees for a number of helpful comments and suggestions.
Notes
A permutation is even (odd) if it has a factorization as a product of an even (odd) number of, not necessarily disjoint, 2-cycles.
A graph is Hamiltonian connected if there is a Hamiltonian path between every pair of vertices.