Take the 2-minute tour ×

Looking into the graph isomorphism problem, after trying to use vertex degree values as anchors for determining isomorphism (Of course failing with regular graphs), the next obvious target was shortest path values.

However, when looking into using shortest path values to determine isomorphisms, it just seems too obvious. It must not work or else someone whould have discovered this already. I just can't see where this fails. I would appreciate if someone could help me see the failure condition.

With any two given graphs G and G', choose any vertex from G at random. Call this vertex Base. From here you can determine the shortest path information of all other vertices relative to the base. Vertices connected to the base have a shortest path of 1. Vertices connected to vertices connected to the base, but not the base, have a shortest path of 2, and so on. To make communication easier, consider the shortest paths as tiers. Shortest paths of 1 are tier 1, while shortest paths of 2 are tier 2 and so on.

This gives very valuable information. Each of the connections of a given vertex can only fall in one of three categories: Connected to same Tier, Connected to Tier +1, and Connected to Tier -1.

There is a non-exponental number of combinations, so it can't require exponential running time to solve. By going through both graphs and using all the vertices as bases, you get invarient graph information that can be used to create an ordered grouping that can be compared to another graph's, to determine if the two are the same.

As I said before, what am I missing? It just can't be that simple, can it?

share|improve this question
It's certainly necessary that if two graphs are isomorphic, you should get similar "shortest path" structures, but how do you know it is sufficient? –  Thomas Andrews Dec 26 '12 at 19:32
Things you say about shortest paths and tiers are correct. What I don't understand is what you mean by "there is a non-exponential number of combinations". Maybe you should describe the proposed algorithm more precisely. –  Dan Shved Dec 26 '12 at 19:32
On another note, of course if you know distances between any two vertices in a graph, you automatically know the graph itself. You don't lose any information when you pass from the graph itself to its matrix of distances. –  Dan Shved Dec 26 '12 at 19:34
I think he means the counts - how many nodes are distance $m$ from $x$? This is an extension of knowing the set of node degrees. –  Thomas Andrews Dec 26 '12 at 19:37
Excluding loops, from the base, there are a number of objects equal to the degree value of the base. The degree value of the Tier 1 objects, -1 when considering the connection to base, remain. Say it's a regular graph with each vertex possessing a degree of 5. That's 5 Tier 1 objects with 4 connections each to work with. The number of possible combinations of these 4 connections is non-exponential. As you move up in tiers, the same rules apply, and the added complexity grows non-exponentially. –  C_Hgn Dec 26 '12 at 20:25
show 1 more comment

1 Answer

up vote 4 down vote accepted

This approach fails on strongly regular graphs. Examples of these can be constructed from Latin squares, as follows. Assume $L$ is an $n\times n$ Latin square with entries from $N=\{1,\ldots,n\}$. The vertices of the associated Latin square graph are the $n^2$ ordered pairs in $N\times N$; two vertices $(i,j)$ and $(k,l)$ are adjacent if $i=k$ or $j=l$ or $L_{i,j}=L_{k,l}$. Any two distinct non-adjacent vertices are at distance two, and are joined by exactly six paths of length two.

share|improve this answer
This is exactly what I was looking for. Thanks! –  C_Hgn Dec 27 '12 at 3:29
Of course you'd really want to provide two latin squares of the same size that produce non-isomorphic graphs, but it shouldn't be too hard. –  Thomas Andrews Dec 27 '12 at 15:38
@thams andrews: Multiplication tables of non-isomorphic groups will work, e.g., $\mathbb{Z}_2^2$ and $\mathbb{Z}_4$. More generally any pair of srg's with the same parameters; Latin square graphs are just the easiest to describe. –  Chris Godsil Dec 27 '12 at 19:15
add comment

Your Answer


