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