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$
5
$\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

| improve this answer | |
$\endgroup$
  • $\begingroup$ this is applicable only to path graphs. $\endgroup$ – Phillip Dukes May 23 '16 at 1:28
  • $\begingroup$ @PhillipDukes It seems to me the commands I posted work for the question the way it is formulated. $\endgroup$ – Anton Antonov May 23 '16 at 1:50
  • $\begingroup$ Yes you are right, I did not see the edit. This is what I need. Nicely done! $\endgroup$ – Phillip Dukes May 23 '16 at 2:36
  • $\begingroup$ @PhillipDukes Great then! :) $\endgroup$ – Anton Antonov May 23 '16 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.