UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Perfect matchings after vertex deletions in n-dimensional lattice graphs Yang, Hangjun


This thesis studies lattice graphs which are readily seen to have many perfect matchings and considers whether if we delete vertices the resulting graphs continue to have perfect matchings. It is clear that one can destroy the property of having a perfect matching by deleting an odd number of vertices, by deleting all the neighbours of a given vertex, etc. Besides these trivial "destructions", in order to guarantee the resulting graph still have perfect matchings, we require the deleted vertices to be mutually far apart. In this thesis, we consider an n-dimensional lattice graph Q(m, n) with bipartition of black and white vertices, where m is even. If the distance of any two deleted black (or white) vertices is greater than 4n(n + l)y/m, then the resulting graph (after vertex deletions) continues to have a perfect matching.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.