[Nauty] all nonisomorphic graphs with 10 vertices

Thomas Ortlepp ortlepp at gmx.de
Thu Oct 10 16:49:02 EST 2002


Hello again,

>> How long does it take, to calculate all
>> nonisomorthic graphs with up to 10
>> vertices by using nauty?

>On my 866 MHz Pentium III (running Linux) it takes 38 seconds.
>It can be done in less than 20 seconds by generating them up
>to 22 edges then adding the complement of each graph.

Its clear to go from 0 to 22 edges and mirror the data,
but your anser is very suprising for me?
Just for 22 edges, you have to generate 45 over 22 different
graphs. These are  4.116.715.363.800  graphs witch have
to sorted by using an isomorpic algorithm.
It is well known, that the number of nonisomorphic graph
for 10 vertices is 12.005.168. Please make sure that you
find this number of graphes?

I am not sure how fast your algorithm is, but if
your calculation is correct I have to take my hat off.

Thomas.





More information about the Nauty mailing list