1
$\begingroup$

I am not form Math field and would like to know if distance matrices of two graphs are equal then those graphs are isomorphic or not or it's an open problem. Any tip for starting point or direction of the proof is also appreciated.

(The distance matrix of a graph is the matrix with the $ij$ entry being the distance between $v_{i}$ and $v_{j}$.)

PS: I prefer to stay away from row/column permutation problem at the moment. Let's assume if two graphs are isomorphic then their nodes are labeled in the same manner.

$\endgroup$
  • $\begingroup$ I would like to extend the question to weighted graphs but first let's assume it's a simple graphs i.e. no weights, no multiple edges and no directions. I certainly need to extend it to weighted later but depending on how easy this one is $\endgroup$ – Kasra Manshaei Jan 4 '18 at 11:44
  • 1
    $\begingroup$ arxiv.org/abs/1510.06952 : They define a neighbour matrix, and prove that isomorphic graphs have the same neighbour matrix but that the converse is not true. $\endgroup$ – gilleain Jan 4 '18 at 12:07
  • $\begingroup$ Thanks gilleain! Very interesting paper! May I ask what was your research that you came up with this paper? We may have the same interest so I can use other resources from you. $\endgroup$ – Kasra Manshaei Jan 4 '18 at 13:49
  • $\begingroup$ Heh. I just googled "non-isomorphic pair graphs same distances" (there could be better search terms!) but I do have an interest in isomorphism of simple graphs and degree sequences, so maybe it was easier for me to find $\endgroup$ – gilleain Jan 4 '18 at 13:52
  • $\begingroup$ Cool! Thanks :) $\endgroup$ – Kasra Manshaei Jan 4 '18 at 13:53
4
$\begingroup$

It is not true for weighted graphs. Take the graph made by three nodes $a,b,c$ with weight matrix: $$\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ \end{matrix}$$ Its distance matrix is $$\begin{matrix} 0 & 1 & 2 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \\ \end{matrix}$$ Now take the graph made by the same set of points but with weight matrix: $$\begin{matrix} 0 & 1 & 2 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \\ \end{matrix}$$ Which is just adding an edge between node $a$ and $c$ with weight 2, now the distance matrix is: $$\begin{matrix} 0 & 1 & 2 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \\ \end{matrix}$$ and it is the same as before but the two graphs are not isomorphic, since they have different adjacents nodes.

EDIT:

Now consider unweighted graphs:

if we allow graphs to have self-loops then the statement is not true, just take a graph without self-loops and then add one self loop.

The two graph will have the same distance matrix since the distance of one node from itself is $0$ and the rest of the graph is the same, but the two graph are not isomorphic.

Now consider two unweighted directed graphs with the same distance matrix, then in order for them to not be isomorphic there must be (at least) one edge that exists in one graph but not in the other (they have the same distance matrix so the number of nodes is the same).

Let's take that edge and let's call the starting node $a$ and the end node $b$, now call $G_1$ the graph with this edge and $G_2$ the graph without it.

Since $G_1$ has the edge then in its distance matrix at the line corresponding to the node $a$ and at the column corresponding to the node $b$ we will have $1$ (the matrix is made by $1$, $0$ and $\infty$ since the graph is unweighted and we can't have $0$ since we are assuming no self-loops and since the edge exists by assumption we can't have $\infty$), but since the distance matrices are the same also the distance matrix of $G_2$ will have the $1$ at that position.

Now we have a path in $G_2$ from $a$ to $b$ which has length $1$, the only way to have that in an unweighted graph is to have the direct edge from $a$ to $b$.

$\endgroup$
  • $\begingroup$ Thanks Chak +1! Very nice example for weighted graphs. So I go on with the same question only for unweighted ones. $\endgroup$ – Kasra Manshaei Jan 4 '18 at 13:52
  • $\begingroup$ Yep, sorry for the missing part, now i will update it. $\endgroup$ – chak Jan 4 '18 at 15:16
  • 2
    $\begingroup$ Essentially, given the distance matrix of an unweighted simple graph, you can recover the adjacency matrix by looking at which entries of the distance matrix are $1$. $\endgroup$ – Misha Lavrov Jan 4 '18 at 16:11
  • $\begingroup$ Thanks Chak! I close this discussion by choosing your answer. Will post the follow up question (which is more difficult I guess) today. $\endgroup$ – Kasra Manshaei Jan 5 '18 at 11:02
2
$\begingroup$

For simple graphs (or digraphs), given a distance matrix $D_{ij}$, by definition:

  • its dimensions determines the number of vertices,
  • there's an edge between (or from) $i$ to $j$ if and only if $D_{ij}=1$.

So it uniquely determines the graph. In fact, by replacing the non-$1$ elements with $0$'s, we get its adjacency matrix.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the answer Rebecca ... +1 :) $\endgroup$ – Kasra Manshaei Jan 5 '18 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.