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

Abstract

<p>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(<em>C_h</em>) and Forb(<em>C²_h</em>) denote the hereditary properties containing graphs with no induced cycle or squared cycle on h vertices, respectively. The edit distance from Forb(<em>C_h</em>) is found for odd values of <em>h</em>, and the maximum edit distance is found for all values of <em>h</em>. The edit distance is found for Forb(<em>C²_h</em>) for <em>h</em> = 8; 9; 10, and the maximum value is known for <em>h</em> = 11; 12, with partial results for other values of <em>h</em>.</p>