Geodesic
Edit distance measure for graphs
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 3, pp. 829-836
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g(n,l)$, the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$. By edit distance of two graphs $G$, $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$. This new extremal number $g(n, l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show that $g(n, l)$ is close to $\frac 12\binom n2$ for small values of $l>2$. We also present some exact values for small $n$ and lower bounds for very large $l$ close to the number of non-isomorphic graphs of $n$ vertices.
In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g(n,l)$, the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$. By edit distance of two graphs $G$, $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$. This new extremal number $g(n, l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show that $g(n, l)$ is close to $\frac 12\binom n2$ for small values of $l>2$. We also present some exact values for small $n$ and lower bounds for very large $l$ close to the number of non-isomorphic graphs of $n$ vertices.
DOI : 10.1007/s10587-015-0211-4
Classification : 05C35, 05C75
Keywords: extremal graph problem; similarity of graphs 
@article{10_1007_s10587_015_0211_4,
     author = {Dzido, Tomasz and Krzywdzi\'nski, Krzysztof},
     title = {Edit distance measure for graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {829--836},
     year = {2015},
     volume = {65},
     number = {3},
     doi = {10.1007/s10587-015-0211-4},
     mrnumber = {3407608},
     zbl = {06537695},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0211-4/}
}
TY  - JOUR
AU  - Dzido, Tomasz
AU  - Krzywdziński, Krzysztof
TI  - Edit distance measure for graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 829
EP  - 836
VL  - 65
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0211-4/
DO  - 10.1007/s10587-015-0211-4
LA  - en
ID  - 10_1007_s10587_015_0211_4
ER  - 
%0 Journal Article
%A Dzido, Tomasz
%A Krzywdziński, Krzysztof
%T Edit distance measure for graphs
%J Czechoslovak Mathematical Journal
%D 2015
%P 829-836
%V 65
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0211-4/
%R 10.1007/s10587-015-0211-4
%G en
%F 10_1007_s10587_015_0211_4
Dzido, Tomasz; Krzywdziński, Krzysztof. Edit distance measure for graphs. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 3, pp. 829-836. doi: 10.1007/s10587-015-0211-4

[1] Alon, N., Shapira, A., Sudakov, B.: Additive approximation for edge-deletion problems. Ann. Math. (2) 170 (2009), 371-411. | MR | Zbl

[2] Alon, N., Spencer, J. H.: The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons, Hoboken (2008). | MR | Zbl

[3] Alon, N., Stav, U.: What is the furthest graph from a hereditary property?. Random Struct. Algorithms 33 (2008), 87-104. | MR | Zbl

[4] Axenovich, M., Kézdy, A., Martin, R.: On the editing distance of graphs. J. Graph Theory 58 (2008), 123-138. | DOI | MR | Zbl

[5] Balogh, J., Martin, R.: Edit distance and its computation. Electron. J. Comb. (electronic only) 15 (2008), Research Paper R20, 27 pages. | MR | Zbl

[6] Chen, D., Eulenstein, O., Fernández-Baca, D., Sanderson, M.: Supertrees by flipping. Computing and Combinatorics; Proc. of the 8th Annual International Conf., Singapore, 2002. O. H. Ibarra et al. Lecture Notes in Comput. Sci. 2387 Springer, Berlin (2002), 391-400. | MR | Zbl

[7] Chung, F. R. K., Erdős, P., Graham, R. L.: Minimal decompositions of graphs into mutually isomorphic subgraphs. Combinatorica 1 (1981), 13-24. | DOI | MR | Zbl

[8] Wet, P. O. de: Constructing a large number of nonisomorphic graphs of order $n$. Morehead Electronic Journal of Applicable Mathematics 1 (2001), 2 pages.

[9] Dzido, T., Krzywdziński, K.: On a local similarity of graphs. Discrete Math. 338 (2015), 983-989. | DOI | MR

Cité par Sources :