- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Perfect matchings after vertex deletions in n-dimensional...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Perfect matchings after vertex deletions in n-dimensional lattice graphs Yang, Hangjun
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.
Item Metadata
Title |
Perfect matchings after vertex deletions in n-dimensional lattice graphs
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2005
|
Description |
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.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2009-12-18
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
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.
|
DOI |
10.14288/1.0080077
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2005-11
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
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.