How can I verify an isomorphism relation between two graphs that join cube and octahedron vertices?

I have two sets of nodes, corresponding to the vertices of the cube (S1 = {1,…,8}) and the octahedron (S2 = {1,…,6}), respectively. I construct each graph G joining vertices of S_1 to vertices of S_2. Having two graphs G_1 and G_2, how can I check if there is an isomorphism relation between these two graphs?

[Catarina Pina]

Example:

Graph G_1: [1 2 3 3 3 4 4 4 5 5 5 6 6 6 7 8],...

[1 1 1 4 5 1 2 5 6 2 3 6 4 3 6 6]);

Graph G_2: [1 2 3 3 3 4 4 4 5 5 5 6 6 6 7 8],...

[3 3 1 4 5 1 2 5 6 2 3 6 4 3 5 5]

Geometrically I see that G_1 and G_2 are isomorphic, but how can I verify using MATLAB? Thanks!

Answer 1

[Steven Lord]

Build the two graph objects then call either isisomorphic or isomorphism on it.

G_1 = graph([1  2  3  3  3  4  4  4  5  5  5  6  6  6  7  8],...
           [1  1  1  4  5  1  2  5  6  2  3  6  4  3  6  6]);
G_2 = graph([1  2  3  3  3  4  4  4  5  5  5  6  6  6  7  8],...
           [3  3  1  4  5  1  2  5  6  2  3  6  4  3  5  5]);
isisomorphic(G_1, G_2)

ans = logical
   0

mapping = isomorphism(G_1, G_2) % Empty if there is no isomorphism

mapping =

     []

Let's look at your two graphs. If you have coordinates for the vertices you could pass them into the plot call by specifying the XData, YData, and (for a 3-D plot) ZData properties rather than letting MATLAB choose the layout itself.

subplot(1, 2, 1)
plot(G_1)
title("G_1")
subplot(1, 2, 2)
plot(G_2)
title("G_2")

Those don't look isomorphic to me. The most obvious difference is that G_1 has two nodes with a self loop while G_2 only has one. In addition the two leaves in G_1 are adjacent to one of the self-loop nodes while the two leaves in G_2 are not adjacent to the self-loop node. Are you sure you assembled the source and target vectors with which I created G_1 and G_2 correctly?

[Christine Tobler]

I think I see what was meant here: The first input and second input to the G_1, G_2 constructors are meant to be addressing two separate sets of nodes (first input is the vertices of the cube, and second input the vertices of the octagon).

You need to add a shift so that the nodes of the octagon are indices 9, 10, ..., 14 instead of reusing the indices 1, 2, ... 6 that are already used for the cube. Then, the two graphs are isomorphic:

G_1 = graph([1  2  3  3  3  4  4  4  5  5  5  6  6  6  7  8],...
           [1  1  1  4  5  1  2  5  6  2  3  6  4  3  6  6]+8);
G_2 = graph([1  2  3  3  3  4  4  4  5  5  5  6  6  6  7  8],...
           [3  3  1  4  5  1  2  5  6  2  3  6  4  3  5  5]+8);
isisomorphic(G_1, G_2)

ans = logical
   1

mapping = isomorphism(G_1, G_2)

mapping = 14x1

1 2 5 6 3 4 7 8 11 12

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

subplot(1, 2, 1)
plot(G_1)
title("G_1")
subplot(1, 2, 2)
plot(G_2)
title("G_2")

[Catarina Pina]

I have tried something similar with digraph, but without sucess. The problem is that there are two disctint sets of indices. In both graphs we have that vertex 1 of cube is connected only with vertex 1 (G_1) or vertex 3 (G_2) of the octaedron. But in graphs representations, we have vertex 1 joining with 1, 2, 3 and 4 (G_1; as vertex 1 of the cube is connected with vertex 1 of the octaedron and vertices 2, 3 and 4 of the cube are connected with vertex 1 of the octaedron) and 3 and 4 (G_2), so I think that thouse representations do not correspond to G_1 and G_2. And I'm not figuring out how to represent these situation.

[Catarina Pina]

Yes, is that! Thank you so much!

[Steven Lord]

Good catch, Christine!