The edit distance function of some graphs

Abstract

The edit distance function of a hereditary property $\mathcal{H}$ is the asymptotically largest edit distance between a graph of density $p\in [0,1]$ and $\mathcal{H}$. 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,\dots ,v_{n-1}\}$ and $E(\widetilde{C_n})=E(C_n)\cup \{v_0{v}_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.

to appear in Discuss. Math. Graph Theory

References in corpus (1)

• On the computation of edit distance functions