Authors: Y. Hu, Y.T. Shi, Y. Wei Title: The edit distance function of some graphs Source: Discussiones Mathematicae Graph Theory Received 05.11.2017, Revised 11.05.2018, Accepted 11.05.2018, doi: 10.7151/dmgt.2154 | |
Abstract: The edit distance function of a hereditary property \mathscr{H} is the asymptotically largest edit distance between a graph of density p∈[0,1] and \mathscr{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}^{*} 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_{0}v_{2}}. Marchant and Thomason determined the edit distance function of C_{6}^{*}. 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}^{*}, \widetilde{C_{n}} and P_{n}, respectively. | |
Keywords: edit distance, colored regularity graphs, hereditary property, clique spectrum | |
Links: |