| Abstrakt: |
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. |
Full text from SpringerLink