Perfect matchings after vertex deletions Original Research Article

This paper considers some classes of graphs which are easily seen to have many perfect matchings. Such graphs can be considered robust with respect to the property of having a perfect matching if under vertex deletions (with some mild restrictions), the resulting subgraph continues to have a perfect matching. It is clear that you can destroy the property of having a perfect matching by deleting an odd number of vertices, by upsetting a bipartition or by deleting enough vertices to create an odd component. One class of graphs we consider is the image lattice graph (or grid graph) for m even. Matchings in such grid graphs correspond to coverings of an image checkerboard by dominoes. If in addition to the easy conditions above, we require that the deleted vertices be image apart, the resulting graph has a perfect matching. The second class of graphs we consider is a k-fold product graph consisting of k copies of a given graph G with the ith copy joined to the imagest copy by a perfect matching joining copies of the same vertex. We show that, apart from some easy restrictions, we can delete any vertices from the kth copy of G and find a perfect matching in the product graph with k suitably large.