most recent 30 from http://mathoverflow.net 2013-05-19T11:02:23Z http://mathoverflow.net/feeds/user/27049 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108976/what-graph-invariants-are-fast-to-compute/109011#109011 azazello 2012-10-06T16:32:00Z 2012-10-06T16:32:00Z

<p>2 Jack: Counting 4-cycles after char poly actually does refine these graphs into smaller groups further down. It <em>seems</em> like counting $k$-cycles for $k\ge 5$ after counting 4-cycles doesn't make much sense.</p> <p>2 Brendan: I'm using the internal facility of sage (an open source project encompassing GAP, Maxima and other open source math-related projects wrapped into a Python framework). I very much believe it's based on the same ideas from your paper that nauty is. So it can't be much worse. Checking the underlying looped undirected graphs obtained by sage's graph.to_undirected() is indeed an easy problem. However even checking whether a pair of graphs corresponding to parameters $(m,n) = (1,3)$ and $(m,n) = (1,3)$ for $q=17$, are isomorphic to each other, proves to be quite hard. </p>