I want to generate all the possible adjacency matrices of equivalent unlabeled graphs. For example, consider the simple path graph of three vertices. There are three possible adjacency matrices:
a1={{0, 1, 0}, {1, 0, 1}, {0, 1, 0}};
a2={{0, 1, 1}, {1, 0, 0}, {1, 0, 0}};
a3={{0, 0, 1}, {0, 0, 1}, {1, 1, 0}};
Each matrix corresponding to a different (numerical) labeling of the vertices.
Is there a way to generate the other representations given any one of them for any simply connected graph?
=================
=================
1 Answer
1
=================
Are you looking for something like the following? How big are your graphs?
First graph from the question
pinds = Permutations[Range[3], {3}];
MatrixPlot /@ Union[a1[[#, #]] & /@ pinds]
AdjacencyGraph[#, VertexLabels -> “Name”] & /@
Union[a1[[#, #]] & /@ pinds]
Larger “seed” graph
Here is another example:
graphRules = {1 <-> 2, 1 <-> 4, 1 <-> 5, 2 <-> 3, 3 <-> 4};
gr = Graph[graphRules, VertexLabels -> “Name”]
a1 = AdjacencyMatrix[gr]
pinds = Permutations[Range[Length[a1]], {Length[a1]}];
MatrixPlot /@ Union[Normal[a1[[#, #]]] & /@ pinds]
AdjacencyGraph[#, VertexLabels -> “Name”] & /@
Union[Normal[a1[[#, #]]] & /@ pinds]
this is applicable only to path graphs.
– Phillip Dukes
May 23 at 1:28
@PhillipDukes It seems to me the commands I posted work for the question the way it is formulated.
– Anton Antonov
May 23 at 1:50
Yes you are right, I did not see the edit. This is what I need. Nicely done!
– Phillip Dukes
May 23 at 2:36
@PhillipDukes Great then! 🙂
– Anton Antonov
May 23 at 2:42