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 Pn and Cn the path graph of order n and the cycle graph of order n, respectively. Let C2n* be the cycle graph C2n with a diagonal, and \widetilde{Cn} be the graph with vertex set {v0, v1, ..., vn-1} and E(\widetilde{Cn})=E(Cn)∪ {v0v2}. Marchant and Thomason determined the edit distance function of C6*. 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*, \widetilde{Cn} and Pn, respectively.
Keywords:
edit distance, colored regularity graphs, hereditary property, clique spectrum

Links:
PDF