## Keywords (2)

Publications
Graph similarity and distance in graphs

# Graph similarity and distance in graphs,10.1007/s000100050025,Aequationes Mathematicae,Gary Chartrand,Grzegorz Kubicki,Michelle Schultz

Graph similarity and distance in graphs
Summary. For connected graphs G1 and G2 of order n and a one-to-one mapping : V (G1)! V (G2), the -distance between G1 and G2 is d(G1;G 2 )= X dG 1 (u;v) dG2 (u;v) ; where the sum is taken over all n 2 unordered pairs u;v of vertices of G1. The distance between G1 and G2 is dened by d(G1;G 2) = minfd(G1;G 2 )g, where the minimum is taken over all oneto-one mappings from V (G1 )t o V ( G 2). It is shown that this distance is a metric on the space of connected graphs of a xed order. The maximum distance D(G1;G 2) = maxfd(G1;G 2 )g for connected graphs G1 and G2 of the same order is also explored. The total distance of a connected graph G is d(u;v), where the sum is taken over all unordered pairs u, v of vertices of G. Bounds for d(G1;G 2) are presented both in terms of the total distances of G1 and G2 and also in terms of the sizes of G1, G2, and a greatest common subgraph of G1 and G2 .F or a set S of connected graphs having xed order, the distance graphD(S )o fSis that graph whose vertex set isS and such that two vertices G 1 and G2 ofD(S) are adjacent if and only if d(G1;G 2 )=1 . Furthermore, a graph G is a distance graph if there exists a setS of graphs having xed order such thatD(S) =G. It is shown that every distance graph is bipartite and, moreover, that all even cycles and all forests are distance graphs. Other bipartite graphs are shown to be distance graphs and it is conjectured that all bipartite graphs are distance graphs.
Journal: Aequationes Mathematicae , vol. 55, no. 1, pp. 129-145, 1998
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
More »

## Citation Context (19)

• ...An example similarity measure based on edit distance has been proposed in [22] addressing graph isomorphism, while [23] addresses subgraph isomorphism...

### Andreas Wombacher, et al. Alternative Approaches for Workflow Similarity

• ...As an attempt to determine the similarity between change workflows, these workflows could be modeled as directed graphs and then have their similarity computed by solutions already employed in general graphs, as in Chartrand et al. [7]...

### Luís Armando Bianchin, et al. Similarity metric for risk assessment in IT change plans

• ...In principle, such a similarity measure can be used in the SCS as well, and other graph similarity measures proposed in the literature (e.g., [6]) are also suitable...

### Sorin M. Iacob, et al. Optimized dynamic semantic composition of services

• ...In [21] Chartrand et al. describe an approach for graph distance calculation based on preserving the distance between nodes...
• ...Given a graph g =( V, E), the distance between two nodes x, y ∈ V , denoted dg(x, y), is defined as the minimum number of edges that need to be traversed when traveling from x to y [21]...
• ...Further, the φ-distance [21] between two graphs g1 an g2, denoted dφ(g1 ,g 2), is defined as dφ(g1 ,g 2 )= �...
• ...In [21] the authors also go on to show that we can make some other, less expensive calculations if the graphs meet certain requirements...
• ...Further theoretical contributions related to this approach can be found in [21]...

### Xiaoyi Jiang, et al. Graph Matching

• ...The geodesic distance d (g, h; G ) between nodes g and h is defied by the length of shortest path from g to h in the graph G. This distance represents the global structure of graph (Chartrand et al., 1988)...
• ...We here note that it is symmetric and satisfies triangle inequality (Chartrand et al., 1988)...

## References (6)

### Average distance in graphs with removed elements(Citations: 7)

Journal: Journal of Graph Theory - JGT , vol. 12, no. 3, pp. 375-390, 1988

### Distances between graphs under edge operations(Citations: 15)

Journal: Discrete Mathematics - DM , vol. 161, no. 1-3, pp. 121-132, 1996

### Existence of graphs with prescribed mean distance(Citations: 3)

Journal: Journal of Graph Theory - JGT , vol. 10, no. 2, pp. 173-175, 1986

### The Wiener polynomial of a graph(Citations: 12)

Published in 1998.

Sort by: