Graph similarity and distance in graphs (Q1381547)

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.