Degree Type

Thesis

Date of Award

2013

Degree Name

Master of Science

Department

Mathematics

First Advisor

Ryan Martin

Abstract

The edit distance from a hereditary property is the fraction of edges in a graph that must be added or deleted for a graph to become a member of that hereditary property. Let Forb(Ch) and Forb(C2h) denote the hereditary properties containing graphs with no induced cycle or squared cycle on h vertices, respectively. The edit distance from Forb(Ch) is found for odd values of h, and the maximum edit distance is found for all values of h. The edit distance is found for Forb(C2h) for h = 8; 9; 10, and the maximum value is known for h = 11; 12, with partial results for other values of h.

Copyright Owner

Chelsea Peck

Language

en

File Format

application/pdf

File Size

76 pages

Included in

Mathematics Commons

Share

COinS