Graph similarity and distance in graphs
type: Item
instance of: scholarly article
title: Graph similarity and distance in graphs
zbMATH Open document ID: 0889.05043
author: Gary Chartrand
author: Michelle Schultz
author: Grzegorz Kubicki
published in: Aequationes Mathematicae
publication date: 1998-05-29T00:00:00Z
review text: For a one-one map \(\phi\) between two connected graphs of the same order their \(\phi\)-distance is the sum over all vertex pairs of the first graph of the absolute difference between their distance and the distance of their \(\phi\)-images. The distance between the graphs is the minimum \(\phi\)-distance over all possible \(\phi\). It is shown this is a metric, lower bounds are obtained and distances are determined for some special graph pairs. A distance graph has as vertices connected graphs of a fixed order and edges indicate a graph distance of 1. Every distance graph is bipartite, and any even cycle, tree, forest and \(K_{2,n}\) is a distance graph. It is conjectured that all bipartite graphs are distance graphs.
reviewed by: Frank Plastria
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1130466
zbMATH Keywords: graph distance
zbMATH Keywords: distance graph
zbMATH Keywords: bipartite graph
MaRDI profile type: Publication
full work available at URL: s000100050025
OpenAlex ID: W1997780247
DOI: 10.1007/S000100050025
description: scientific article; zbMATH DE number 1130466