[Nauty-list] Hard Instances

Greg Tener boris at cfl.rr.com
Wed Mar 21 14:18:55 EST 2007


I have three questions about hard instances for nauty (they're so few 
and hard to find).

I have found most of the planes at 
http://www.uwyo.edu/moorhouse/pub/planes27/ to be difficult, some are 
easier with using invariants such as cellfano and cellfano2.

Hadamard equivalence of Hadamard matrices are mentioned in the new users 
guide as well as a citing of a paper that describes a family requiring 
exponential growth of the number of nodes.

So, which Hadamard matrices in particular are hard? I've found some at 
Neil Sloane's site.

Also, are there any graphs with trivial automorphism group known to be 
hard for nauty?

Are there any other notable graphs which take a long time?

University of Central Florida
-Greg Tener-




More information about the Nauty mailing list