𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the editing distance of graphs

✍ Scribed by Maria Axenovich; André Kézdy; Ryan Martin

Publisher
John Wiley and Sons
Year
2008
Tongue
English
Weight
169 KB
Volume
58
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

On the distance matrix of a directed gra
On the distance matrix of a directed graph
✍ R. L. Graham; A. J. Hoffman; H. Hosoya 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

## Abstract In this note, we show how the determinant of the distance matrix __D(G__) of a weighted, directed graph __G__ can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks __G~i~__ of __G__. In particular, when cof __D(G__), the sum of the cofactors of _

HMM-based graph edit distance for image
HMM-based graph edit distance for image indexing
✍ Bing Xiao; Xinbo Gao; Dacheng Tao; Xuelong Li 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 386 KB 👁 1 views

## Abstract Most of the existing graph edit distance (GED) algorithms require cost functions which are difficult to be defined exactly. In this article, we propose a cost function free algorithm for computing GED. It only depends on the distribution of nodes rather than node or edge attributes in g

Distance graphs with missing multiples i
Distance graphs with missing multiples in the distance sets
✍ Liu, Daphne D.-F.; Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 3 views

Given positive integers m, k, and s with m > ks, let D m,k,s represent the set {1, 2, . . . , m} -{k, 2k, . . . , sk}. The distance graph G(Z, D m,k,s ) has as vertex set all integers Z and edges connecting i and j whenever |i -j| ∈ D m,k,s . The chromatic number and the fractional chromatic number

The average Steiner distance of a graph
The average Steiner distance of a graph
✍ Dankelmann, Peter; Oellermann, Ortrud R.; Swart, Henda C. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB 👁 1 views

The average distance p(G) of a graph G is the average among the distances between all pairs of vertices in G. For n 2 2, the average Steiner n-distance ,4G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, pu,