While isomorphisms between graphs are not unique, they have an exactness that I would like to relax to a metric. Instead of considering 'whether' two graphs are isomorphic, I would like to consider how close they are to being isomorphic. I might have found a way to do this, but is my reasoning correct?
My thinking on the matter is that given two graphs $G$ and $H$, I would like to find a bijection $f:V(G) \rightarrow V(H)$ such that $\sum_{u\in V(G)}|deg(f(u)) – deg(u)|$ minimized. However, this would not actually be defined on all graphs $G$ and $H$ because $|V(G)| = |V(H)|$ does not hold in for all graphs.
To generalize to graphs of different sizes, I reconsider for such a pair of graphs where $|V(G)| \neq |V(H)|$ if I might instead find a bijection between an induced subgraph of G and an induced subgraph of H such that the cardinality of the vertex set for both induced subgraphs is equal to $\min (|V(G)|, |V(H)|)$ and that the sum of the degree distances as previously mentioned is minimized by the choices of bijection and induced subgraphs. This leaves $||V(G)| – |V(H)||$ unaccounted for in the metric, so to incorporate them it makes sense to me to add the sum of the degrees of the vertices not participating in the bijection as part of the metric. This still allows for there to be a zero distance for non-isometric graphs when the unmapped vertices are completely disconnected, so perhaps also adding the number of excluded vertices to the proposed metric would ensure that there's always a non-zero cost to not using all the vertices.
Does this approach really quantify how non-isomorphic two graphs are on their adjacency structure?
Best Answer
Here is an example of two non-isomorphic graphs that are at distance $0$ by your definition:
Both graphs have $6$ vertices, all of degree $3$. But the left one is $K_{3,3}$, a bipartite graph; the right one is not bipartite because, in particular, it has two clearly visible triangles. This is one way to see that they're not isomorphic. (You can also look at their complements; the complement of the right graph is connected and the complement of the left graph isn't.)
In general, for large $k$ and $n$, if there are any $k$-regular graphs on $n$ vertices, there are lots.
One measure I might suggest is "edit distance" between two graphs: the number of times you need to perform some well-defined operation (for example, adding or removing an edge or an isolated vertex) to turn one graph into something isomorphic to the other.