Go to  Advanced Search

Perfect matchings after vertex deletions in n-dimensional lattice graphs

Show full item record

Files in this item

Files Size Format Description   View
ubc_2005-0708.pdf 1.641Mb Adobe Portable Document Format   View/Open
 
Title: Perfect matchings after vertex deletions in n-dimensional lattice graphs
Author: Yang, Hangjun
Degree Master of Science - MSc
Program Mathematics
Copyright Date: 2005
Abstract: 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.
URI: http://hdl.handle.net/2429/16911
Series/Report no. UBC Retrospective Theses Digitization Project [http://www.library.ubc.ca/archives/retro_theses/]

This item appears in the following Collection(s)

Show full item record

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893