4
$\begingroup$

In graph theory, an isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$ ${\displaystyle f\colon V(G)\to V(H)}$ such that any two vertices $u$ and $v$ of $G$ are adjacent in $G$ if and only if ${\displaystyle f(u)}$ and ${\displaystyle f(v)}$ are adjacent in $H$. We know that IsomorphicGraphQ can return True if two graphs $G$ and $H$ are isomorphic, False otherwise. We can use FindGraphIsomorphism to find an isomorphic mapping of $G$ and $H$.

My problem is that if two graphs are not isomorphic, the IsomorphicGraphQ will only return False. Its correctness cannot be checked manually. I was wondering if IsomorphicGraphQ could give some additional information to help us understand why these two graphs are not isomorphic.

The following just a simple example. We can say that the first graph has a cycle and the second graph has no cycle, so the two graphs are not isomorphic.

g = CycleGraph[5];
h = PathGraph[Range[5]];
IsomorphicGraphQ[g, h]

I actually came across the next two planar graphs.

G1 = Graph[
   ImportString["W{`I@CoC?o`_@_?o?K?@`?C??KG?K??EC?@_??EG??[???N", 
    "Graph6"], VertexLabels -> Automatic];
G2 = Graph[
   ImportString["WspB@CoC?o`_@@@_?GGB??KC?O??WG?CK?B_??K???W_??N", 
    "Graph6"], VertexLabels -> Automatic];
IsomorphicGraphQ[G1, G2]

False

In general, I trust the results returned by IsomorphicGraphQ, but I wish it can provide more readable information.

$\endgroup$
5
  • $\begingroup$ What kind of certificate do you propose could be used to show non-isomorphism? $\endgroup$
    – Szabolcs
    Commented May 5, 2022 at 8:38
  • $\begingroup$ Perhaps in some cases you could look at the number of automorphisms for each graph. With built-ins: GroupOrder@GraphAutomorphismGroup[g]. With IGraph/M: IGBlissAutomorphismCount[g]. GroupOrbits also provides useful information: there are two orbits in G1, but only one in G2. $\endgroup$
    – Szabolcs
    Commented May 5, 2022 at 8:41
  • $\begingroup$ My ideas may be immature. For example one graph contains a special graph $H$ as a subgraph and another graph does not contain $H$ . The worst case might be to go through all the mappings and check one by one. $\endgroup$
    – licheng
    Commented May 5, 2022 at 8:46
  • $\begingroup$ Okay, but showing that it does not contain $H$ is again difficult. $\endgroup$
    – Szabolcs
    Commented May 5, 2022 at 8:48
  • $\begingroup$ I asked this question because I wanted to show that two graphs in the last paragraph of the question are not isomorphic in my paper. I 'd like to use MMA to give me a hint rather than directly using its result. $\endgroup$
    – licheng
    Commented May 5, 2022 at 8:49

1 Answer 1

4
$\begingroup$

Here are some ideas that might work.

We are looking for a computation that is simple enough that we can trust its output, and can potentially show that two graphs are non-isomorphic. The simplest way is to look at the vertex degrees. In your example, they are the same: both G1 and G2 are 4-regular. But we can also count 2nd, 3rd, etc. neighbours, and see if we discover a difference. One easy way to do it is with IGConnectNeighborhood from IGraph/M, which connected each vertex to all vertices no more than distance k away. The size of the 2nd order neighbourhood is 11 for all vertices for both graphs. But for the 3rd order neighbourhood, we see differences:

VertexDegree@IGConnectNeighborhood[G1, 3]
(* {18, 19, 18, 18, 18, 19, 19, 18, 18, 19, 18, 18, 19, 18, \
18, 19, 19, 18, 18, 18, 18, 19, 18, 18} *)

VertexDegree@IGConnectNeighborhood[G2, 3]
(* {18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, \
18, 18, 18, 18, 18, 18, 18, 18, 18, 18} *)

This proves, in a reasonably straightforward manner, that the two graphs are no isomorphic.


An interesting question, which I do not have the answer to, is: Is there a pair of non-isomorphic graphs where the number of neighbours is identical at all distances?

Update: There are pairs of graphs where the number of neighbours is the same at all distances. The smallest example seems to be this pair:

g1 = IGShorthand["1,2,3,4,5,2-1-3-4-2,1-5-4"]
g2 = IGShorthand["1,2,3,4,5,1-4-3-2-1-5-4"]

enter image description here

enter image description here

Let us write a "signature" function that takes a connected undirected graph and counts the number of neighbours at each distance up to the diameter:

sig[g_] := Module[{dm, diam},
  dm = GraphDistanceMatrix[g];
  diam = Max[dm];
  Sort[Lookup[Counts[#], Range[diam], 0] & /@ dm]
]

This is the same for the above two graphs. Without sorting, the signature is {{3, 1}, {2, 2}, {2, 2}, {3, 1}, {2, 2}} for both graphs, yet they are not isomorphic: g1 does not have a cycle of length 3, but g2 does.

A more interesting example pair of regular graphs is ImportString["FFzvO\nFUzro" , "Graph6"].


It is useful to note that many isomorphism testing programs, including the one used by Mathematica, as well as Bliss (exposed through IGraph/M), compute a canonical form of graphs. See CanonicalGraph and IGBlissCanonicalGraph, IGBlissCanonicalLabeling, IGBlissCanonicalPermutation. Two graphs are isomorphic precisely when their canonical form is the same.

In my opinion, however, checking that the canonicalized forms are different does not provide additional confidence that the graphs are not isomorphic. The canonical labeller could be buggy as well.

$\endgroup$
3
  • $\begingroup$ Your analysis is brilliant, and so is the question at the end. $\endgroup$
    – licheng
    Commented May 5, 2022 at 8:57
  • 1
    $\begingroup$ @licheng Unfortunately, there is a small example where the neighbour counts are identical at each distance, yet the graphs are not isomorphic. I updated the answer. $\endgroup$
    – Szabolcs
    Commented May 5, 2022 at 9:19
  • $\begingroup$ Yeah. Anyway, your analysis has opened my mind. We can analyze two graphs after doing some graph operations on the original graphs separately. That's a brilliant idea. $\endgroup$
    – licheng
    Commented May 5, 2022 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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