
arXiv: 1012.3716
The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets. The edit distance function of the hereditary property, $\mathcal{H}$, is a function of $p\in[0,1]$ and is the limit of the maximum normalized distance between a graph of density $p$ and $\mathcal{H}$. This paper uses the symmetrization method of Sidorenko in order to compute the edit distance function of various hereditary properties. For any graph $H$, ${\rm Forb}(H)$ denotes the property of not having an induced copy of $H$. We compute the edit distance function for ${\rm Forb}(H)$, where $H$ is any split graph, and the graph $H_9$, a graph first used to describe the difficulties in computing the edit distance function.
25 pages, 2 figures
Extremal problems in graph theory, symmetrization, Distance in graphs, split graph, edit distance, Coloring of graphs and hypergraphs, Graph algorithms (graph-theoretic aspects), 05C35, 05C80, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), hereditary property, colored regularity graph
Extremal problems in graph theory, symmetrization, Distance in graphs, split graph, edit distance, Coloring of graphs and hypergraphs, Graph algorithms (graph-theoretic aspects), 05C35, 05C80, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), hereditary property, colored regularity graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
