Premium
On the editing distance of graphs
Author(s) -
Axenovich Maria,
Kézdy André,
Martin Ryan
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20296
Subject(s) - combinatorics , mathematics , vertex (graph theory) , discrete mathematics , pathwidth , graph , line graph
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