| Title:
|
Edit distance measure for graphs (English) |
| Author:
|
Dzido, Tomasz |
| Author:
|
Krzywdziński, Krzysztof |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
3 |
| Year:
|
2015 |
| Pages:
|
829-836 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
extremal graph problem |
| Keyword:
|
similarity of graphs |
| MSC:
|
05C35 |
| MSC:
|
05C75 |
| idZBL:
|
Zbl 06537695 |
| idMR:
|
MR3407608 |
| DOI:
|
10.1007/s10587-015-0211-4 |
| . |
| Date available:
|
2015-10-04T18:22:42Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144446 |
| . |
| Reference:
|
[1] Alon, N., Shapira, A., Sudakov, B.: Additive approximation for edge-deletion problems.Ann. Math. (2) 170 (2009), 371-411. Zbl 1185.05132, MR 2521119 |
| Reference:
|
[2] Alon, N., Spencer, J. H.: The Probabilistic Method.Wiley-Interscience Series in Discrete Mathematics and Optimization John Wiley & Sons, Hoboken (2008). Zbl 1148.05001, MR 2437651 |
| Reference:
|
[3] Alon, N., Stav, U.: What is the furthest graph from a hereditary property?.Random Struct. Algorithms 33 (2008), 87-104. Zbl 1146.05046, MR 2428979 |
| Reference:
|
[4] Axenovich, M., Kézdy, A., Martin, R.: On the editing distance of graphs.J. Graph Theory 58 (2008), 123-138. Zbl 1156.05027, MR 2407000, 10.1002/jgt.20296 |
| Reference:
|
[5] Balogh, J., Martin, R.: Edit distance and its computation.Electron. J. Comb. (electronic only) 15 (2008), Research Paper R20, 27 pages. Zbl 1159.05030, MR 2383440 |
| Reference:
|
[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. Zbl 1077.92514, MR 2064534 |
| Reference:
|
[7] Chung, F. R. K., Erdős, P., Graham, R. L.: Minimal decompositions of graphs into mutually isomorphic subgraphs.Combinatorica 1 (1981), 13-24. Zbl 0491.05049, MR 0602412, 10.1007/BF02579173 |
| Reference:
|
[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. |
| Reference:
|
[9] Dzido, T., Krzywdziński, K.: On a local similarity of graphs.Discrete Math. 338 (2015), 983-989. MR 3318633, 10.1016/j.disc.2015.01.016 |
| . |
