Back to search

University of Victoria (Canada)

On graph-transverse matching problems

Abstract

dc:description.abstract

Given graphs G,H, is it possible to find a matching which, when deleted from G, destroys all copies of H? The answer is obvious for some inputs—notably, when G is a large complete graph the answer is “no”—but in general this can be a very difficult question. In this thesis, we study this decision problem when H is a fixed tree or cycle; our aim is to identify those H for which it can be solved efficiently. The H-transverse matching problem, TM(H) for short, asks whether an input graph admits a matching M such that no subgraph of G − M is isomorphic to H. The main goal of this thesis is the following dichotomy. When H is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an H-transverse matching if one exists. However, TM(H) is NP-complete when H is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Mathematics and Statistics
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Churchley, Ross William
Advisor dc:contributor.supervisor
  • Huang, Jing

Subjects

dc:subject × 4

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1828/4137

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Churchley, Ross William. On graph-transverse matching problems. Master of Science M.Sc. thesis, 2012. http://hdl.handle.net/1828/4137