2
$\begingroup$

I am working on a Mathematica program that involves taking a graph and generating all of its single-edge contractions.

When I get this list of contractions, it often happens that many of the graphs in the list are isomorphic. I am wondering if there is a way for Mathematica to throw out all of the extra graphs in my list that are isomorphic duplicates.

Additionally, I need to be able to take two lists of graphs and test to see if the two lists have any isomorphic graphs in common. I think I will run into the same problem here, where Mathematica thinks that graphs with differently named vertices are different when they are really isomorphic.

Edit

I just want to add that I am very new to Mathematica. I am aware of the GraphIsomorphismQ function but I am not sure how to use it for the purposes described above.

I have tried the DeleteDuplicates function to remove isomorphic graphs from a list, but it did not work.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Learning Mathematica requires effort (as is the case with almost everything else). Have you tried something? Can you show it? $\endgroup$
    – Dr. belisarius
    Feb 25, 2016 at 4:25

1 Answer 1

Reset to default
6
$\begingroup$

Take a look at the second argument of DeleteDuplicates: it is the function used to test if two elements are the same.

Thus you can use

DeleteDuplicates[list, IsomorphicGraphQ]

to filter out duplicate graphs.

Be aware of this bug in IsomorphicGraphQ (and consider complaining to Wolfram about it if it affects you):

Improve this answer
$\endgroup$

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