2
$\begingroup$

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?

$\endgroup$

1 Answer 1

6
$\begingroup$

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]

enter code here

Larger "seed" graph

Here is another example:

graphRules = {1 <-> 2, 1 <-> 4, 1 <-> 5, 2 <-> 3, 3 <-> 4};
gr = Graph[graphRules, VertexLabels -> "Name"]

enter image description here

a1 = AdjacencyMatrix[gr]

pinds = Permutations[Range[Length[a1]], {Length[a1]}];

MatrixPlot /@ Union[Normal[a1[[#, #]]] & /@ pinds]

enter image description here

AdjacencyGraph[#, VertexLabels -> "Name"] & /@ 
 Union[Normal[a1[[#, #]]] & /@ pinds]

enter image description here

$\endgroup$
4
  • $\begingroup$ this is applicable only to path graphs. $\endgroup$ May 23, 2016 at 1:28
  • $\begingroup$ @PhillipDukes It seems to me the commands I posted work for the question the way it is formulated. $\endgroup$ May 23, 2016 at 1:50
  • $\begingroup$ Yes you are right, I did not see the edit. This is what I need. Nicely done! $\endgroup$ May 23, 2016 at 2:36
  • $\begingroup$ @PhillipDukes Great then! :) $\endgroup$ May 23, 2016 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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