Name
Abstract | ||
|---|---|---|
An edge-operation on a graph G is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs $\cal G$, the editing distance from G to $\cal G$ is the smallest number of edge-operations needed to modify G into a graph from $\cal G$. In this article, we fix a graph H and consider Forb(n, H), the set of all graphs on n vertices that have no induced copy of H. We provide bounds for the maximum over all n-vertex graphs G of the editing distance from G to Forb(n, H), using an invariant we call the binary chromatic number of the graph H. We give asymptotically tight bounds for that distance when H is self-complementary and exact results for several small graphs H. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:123–138, 2008 |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1002/jgt.v58:2 | Journal of Graph Theory |
Keywords | Field | DocType |
edit distance,random graphs | Random regular graph,Discrete mathematics,Combinatorics,Graph power,Chordal graph,Graph product,Cograph,Symmetric graph,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
58 | 2 | J. Graph Theory 58(2) (2008), pp. 123--138 |
Citations | PageRank | References |
14 | 1.06 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Axenovich | 1 | 209 | 33.90 |
| André E. Kézdy | 2 | 75 | 15.54 |
| Ryan Martin | 3 | 144 | 14.43 |