Geodesic
The Edit Distance Function of Some Graphs
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 807-821

Voir la notice de l'article provenant de la source Library of Science

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 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 C_n be the graph with vertex set v_0, v_1, . . ., v_n−1 and E(C_n)=E(C_n)∪v_0v_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^∗, C_n and P_n, respectively.
Keywords: edit distance, colored regularity graphs, hereditary property, clique spectrum 
@article{DMGT_2020_40_3_a7,
     author = {Hu, Yumei and Shi, Yongtang and Wei, Yarong},
     title = {The {Edit} {Distance} {Function} of {Some} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {807--821},
     publisher = {mathdoc},
     volume = {40},
     number = {3},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a7/}
}
TY  - JOUR
AU  - Hu, Yumei
AU  - Shi, Yongtang
AU  - Wei, Yarong
TI  - The Edit Distance Function of Some Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 807
EP  - 821
VL  - 40
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a7/
LA  - en
ID  - DMGT_2020_40_3_a7
ER  - 
%0 Journal Article
%A Hu, Yumei
%A Shi, Yongtang
%A Wei, Yarong
%T The Edit Distance Function of Some Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 807-821
%V 40
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a7/
%G en
%F DMGT_2020_40_3_a7
Hu, Yumei; Shi, Yongtang; Wei, Yarong. The Edit Distance Function of Some Graphs. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 3, pp. 807-821. http://geodesic.mathdoc.fr/item/DMGT_2020_40_3_a7/