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/

[1] N. Alon, Testing subgraphs in large graphs, Random Structures Algorithms 21 (2002) 359–370. doi:10.1002/rsa.10056

[2] N. Alon, A. Duke, H. Lefmann, V. Rödl and R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994) 80–109. doi:10.1006/jagm.1994.1005

[3] N. Alon, M. Krivelevich, E. Fischer and M. Szegedy, Efficient testing of large graphs, in: Proc. 40th Symposium on Foundations of Computer Science) (IEEE Press, 1999) 656–666.

[4] N. Alon and U. Stav, What is the furthest graph from a hereditary property?, Random Structures Algorithms 33 (2008) 87–104. doi:10.1002/rsa.20209

[5] M. Axenovich, A. Kézdy and R. Martin, On the editing distance of graphs, J. Graph Theory 58 (2008) 123–138. doi:10.1002/jgt.20296

[6] J. Balogh and R. Martin, Edit distance and its computation, Electron. J. Combin. 15 (2008) #R20.

[7] Z. Berikkyzy, R. Martin and C. Peck, On the edit distance of powers of cycles, submitted. arXiv:1509.07438

[8] J.A. Bondy and U.S.R. Murty, Graph Theory (New York, Springer, 2008).

[9] D. Chen, O. Eulenstein, D. Fernández-Baca and M. Sanderson, Supertrees by flip-ping, in: O.H. Ibarra, L. Zhang (Eds.) Computing and Combinatorics, Lectures Notes in Comput. Sci. 2387 (2002) 391–400. doi:10.1007/3-540-45655-4_42

[10] E. Marchant and A. Thomason, Extremal graphs and multigraphs with two weighted colours, in: Fete of Combinatorics and Computer Science, Springer (2010) 239–286. doi:10.1007/978-3-642-13580-4_10

[11] R. Martin, The edit distance in graphs: Methods, results, and generalizations, in: Recent Trends in Combinatorics, Springer (2016) 31–62. doi:10.1007/978-3-319-24298-9_2

[12] R. Martin, On the computation of edit distance functions, Discrete Math. 338 (2015) 291–305. doi:10.1016/j.disc.2014.09.005

[13] R. Martin, The edit distance function and symmetrization, Electron. J. Combin. 20 (2013) #P26.

[14] R. Martin and T. McKay, On the edit distance from K2,t-free graphs, J. Graph Theory 77 (2014) 117–143. doi:10.1002/jgt.21777

[15] C. Peck, On the Edit Distance from a Cycle- and Squared Cycle-Free Graph (Master’s Thesis, Iowa State University, 2013).