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

6 views (last 30 days)
Catarina Pina on 4 Jun 2024
Commented: Steven Lord on 4 Jun 2024
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 on 4 Jun 2024
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!

Steven Lord on 4 Jun 2024
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?
Catarina Pina on 4 Jun 2024
Yes, is that! Thank you so much!
Steven Lord on 4 Jun 2024
Good catch, Christine!

### Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

R2022b

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!