On the edit distance from a cycle- and squared cycle-free graph

Thumbnail Image
Date
2013-01-01
Authors
Peck, Chelsea
Major Professor
Advisor
Ryan Martin
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Journal Issue
Is Version Of
Versions
Series
Department
Mathematics
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.

Comments
Description
Keywords
Citation
DOI
Source
Subject Categories
Copyright
Tue Jan 01 00:00:00 UTC 2013