1. The Edit Distance Function of Some Graphs
- Author
-
Hu Yumei, Shi Yongtang, and Wei Yarong
- Subjects
edit distance ,colored regularity graphs ,hereditary property ,clique spectrum ,05c35 ,Mathematics ,QA1-939 - 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.
- Published
- 2020
- Full Text
- View/download PDF