Edit distance measure for graphs
- 1 September 2015
- journal article
- Published by Institute of Mathematics, Czech Academy of Sciences in Czechoslovak Mathematical Journal
- Vol. 65 (3) , 829-836
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}\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)\) 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.
Keywords
This publication has 7 references indexed in Scilit:
- On a local similarity of graphsDiscrete Mathematics, 2015
- Additive approximation for edge-deletion problemsAnnals of Mathematics, 2009
- The Probabilistic Method2008
- What is the furthest graph from a hereditary property?Random Structures & Algorithms, 2008
- On the editing distance of graphsJournal of Graph Theory, 2008
- Supertrees by Flipping2002
- Minimal decompositions of graphs into mutually isomorphic subgraphsCombinatorica, 1981