The Edit Distance Function of Some Graphs

The edit distance function of a hereditary property $ℋ$ is the asymptotically largest edit distance between a graph of density $p ∈ [0, 1]$ and $ℋ$. Denote by $P_n$ and $C_n$ the path graph of order $n$ and the cycle graph of order $n$, respectively. Let \(C_{2n}^\ast\) be the cycle graph $C_{2n}$ with a diagonal, and \(\widetilde{C_n}\) be the graph with vertex set ${v_0, v_1, . . ., v_{n−1}}$ and \(E(\widetilde{C_n})=E(C_n)∪{v_0v_2}\). Marchant and Thomason determined the edit distance function of \(C_6^\ast\). Peck studied the edit distance function of $C_n$, while Berikkyzy et al. studied the edit distance of powers of cycles. In this paper, by using the methods of Peck and Martin, we determine the edit distance function of \(C_8^\ast\), \(\widetilde{C_n}\) and $P_n$, respectively.