Graph similarity and distance in graphs

Summary.

For connected graphs G ₁ and G ₂ of order n and a one-to-one mapping $\phi : V (G_1) \to V (G_2)$, the $\phi$-distance between G ₁ and G ₂ is ¶¶ $ d_ \phi (G_1, G_2) = \sum \bigl| d_{G_1} (u,v) - d_{G_2} (\phi u, \phi v)\bigr|, $¶¶ where the sum is taken over all ${n \choose 2}$ unordered pairs u,v of vertices of G ₁. The distance between G ₁ and G ₂ is defined by $d (G_1, G_2) = \min \{ d_\phi(G_1, G_2)\}$, where the minimum is taken over all one-to-one mappings $\phi$ from V (G ₁) to V (G ₂). It is shown that this distance is a metric on the space of connected graphs of a fixed order. The maximum distance $D (G_1, G_2) = \max \{ d_\phi(G_1, G_2)\}$ for connected graphs G ₁ and G ₂ of the same order is also explored. The total distance of a connected graph G is $\Sigma d(u,v)$, where the sum is taken over all unordered pairs u, v of vertices of G. Bounds for d (G ₁, G ₂) are presented both in terms of the total distances of G ₁ and G ₂ and also in terms of the sizes of G ₁, G ₂, and a greatest common subgraph of G ₁ and G ₂. For a set $\cal {S}$ of connected graphs having fixed order, the distance graph $\cal {D} (\cal {S})$ of $\cal {S}$ is that graph whose vertex set is $\cal {S}$ and such that two vertices G ₁ and G ₂ of $\cal {D}( \cal {S})$ are adjacent if and only if d (G ₁, G ₂) = 1. Furthermore, a graph G is a distance graph if there exists a set $\cal {S}$ of graphs having fixed order such that $\cal {D} (\cal {S}) \cong 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.