The Edit Distance Function of Some Graphs

Abstract

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 Pn and Cn the path graph of order n and the cycle graph of order n, respectively. Let C2n*C_{2n}^* be the cycle graph C2n with a diagonal, and C˜n{\tilde C_n} be the graph with vertex set {v0, v1, . . . , vn−1} and E(C˜n)=E(Cn)∪{v0v2}E\left( {{{\tilde C}_n}} \right) = E\left( {{C_n}} \right) \cup \left\{ {{v_0}{v_2}} \right\}. Marchant and Thomason determined the edit distance function of C6*C_6^*. Peck studied the edit distance function of Cn, 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 C8*C_8^*, C˜n{\tilde C_n} and Pn, respectively.

Keywords

• edit distance
• colored regularity graphs
• hereditary property
• clique spectrum
• 05c35