Edit distance measure for graphs

Tomasz Dzido; Krzysztof Krzywdziński

Czechoslovak Mathematical Journal (2015)

  • Volume: 65, Issue: 3, page 829-836
  • ISSN: 0011-4642

Abstract

top
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 1 2 n 2 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.

How to cite

top

Dzido, Tomasz, and Krzywdziński, Krzysztof. "Edit distance measure for graphs." Czechoslovak Mathematical Journal 65.3 (2015): 829-836. <http://eudml.org/doc/271811>.

@article{Dzido2015,
abstract = {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\{1\}\{2\}\binom\{n\}\{2\}$ 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.},
author = {Dzido, Tomasz, Krzywdziński, Krzysztof},
journal = {Czechoslovak Mathematical Journal},
keywords = {extremal graph problem; similarity of graphs},
language = {eng},
number = {3},
pages = {829-836},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Edit distance measure for graphs},
url = {http://eudml.org/doc/271811},
volume = {65},
year = {2015},
}

TY - JOUR
AU - Dzido, Tomasz
AU - Krzywdziński, Krzysztof
TI - Edit distance measure for graphs
JO - Czechoslovak Mathematical Journal
PY - 2015
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 3
SP - 829
EP - 836
AB - 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{1}{2}\binom{n}{2}$ 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.
LA - eng
KW - extremal graph problem; similarity of graphs
UR - http://eudml.org/doc/271811
ER -

References

top
  1. Alon, N., Shapira, A., Sudakov, B., Additive approximation for edge-deletion problems, Ann. Math. (2) 170 (2009), 371-411. (2009) Zbl1185.05132MR2521119
  2. Alon, N., Spencer, J. H., The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons, Hoboken (2008). (2008) Zbl1148.05001MR2437651
  3. Alon, N., Stav, U., What is the furthest graph from a hereditary property?, Random Struct. Algorithms 33 (2008), 87-104. (2008) Zbl1146.05046MR2428979
  4. Axenovich, M., Kézdy, A., Martin, R., 10.1002/jgt.20296, J. Graph Theory 58 (2008), 123-138. (2008) Zbl1156.05027MR2407000DOI10.1002/jgt.20296
  5. Balogh, J., Martin, R., Edit distance and its computation, Electron. J. Comb. (electronic only) 15 (2008), Research Paper R20, 27 pages. (2008) Zbl1159.05030MR2383440
  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. (2002) Zbl1077.92514MR2064534
  7. Chung, F. R. K., Erdős, P., Graham, R. L., 10.1007/BF02579173, Combinatorica 1 (1981), 13-24. (1981) Zbl0491.05049MR0602412DOI10.1007/BF02579173
  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. (2001) 
  9. Dzido, T., Krzywdziński, K., 10.1016/j.disc.2015.01.016, Discrete Math. 338 (2015), 983-989. (2015) MR3318633DOI10.1016/j.disc.2015.01.016

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.