×

Perfect matchings after vertex deletions. (English) Zbl 1126.05077

Summary: 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 \(m\times m\) lattice graph (or grid graph) for \(m\) even. Matchings in such grid graphs correspond to coverings of an \(m\times m\) checkerboard by dominoes. If in addition to the easy conditions above, we require that the deleted vertices be \(\Theta (\sqrt m)\) 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 \(i\)th copy joined to the (\(i+1\))st 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 \(k\)th copy of \(G\) and find a perfect matching in the product graph with \(k\) suitably large.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aldred, R. E.L.; Plummer, M. D., On matching extensions with prescribed and proscribed edge sets. II, 16th British Combinatorial Conference (London, 1997), Discrete Math., 197/198, 29-40 (1999) · Zbl 0929.05068
[2] Aldred, R. E.L.; Plummer, M. D., Edge proximity and matching extension in planar triangulations, Australas. J. Combin., 29, 215-224 (2004) · Zbl 1048.05066
[3] Hall, P., On representatives of subsets, J. London Math. Soc., 10, 26-30 (1935) · Zbl 0010.34503
[4] R.E. Jamison, Natalie Lockner, Tiling fringed chessboards with dominoes, 34th Southeastern International Conference on Combinatorics, Graph Theory Comp.; R.E. Jamison, Natalie Lockner, Tiling fringed chessboards with dominoes, 34th Southeastern International Conference on Combinatorics, Graph Theory Comp.
[5] L. Lovász, M.D. Plummer, Matching Theory, North-Holland Mathematics Studies, vol. 121, Annals of Discrete Mathematics, vol. 29, North-Holland Publishing Co., Amsterdam, Akadémiai Kiadó (Publishing House of the Hungarian Academy of Sciences), Budapest, 1986, \( \operatorname{xxvii} + 544 \operatorname{pp} \); L. Lovász, M.D. Plummer, Matching Theory, North-Holland Mathematics Studies, vol. 121, Annals of Discrete Mathematics, vol. 29, North-Holland Publishing Co., Amsterdam, Akadémiai Kiadó (Publishing House of the Hungarian Academy of Sciences), Budapest, 1986, \( \operatorname{xxvii} + 544 \operatorname{pp} \)
[6] Plummer, M. D., On \(n\)-extendable graphs, Discrete Math., 31, 2, 201-210 (1980) · Zbl 0442.05060
[7] Porteous, M. I.; Aldred, R. E.L., Matching extensions with prescribed and forbidden edges, Australas. J. Combin., 13, 163-174 (1996) · Zbl 0852.05068
[8] Tutte, W. T., The factorization of linear graphs, J. London Math. Soc., 22, 107-111 (1947) · Zbl 0029.23301
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.