[Nauty] multigraphs

Sterten at aol.com Sterten at aol.com
Tue Sep 21 16:16:01 EST 2004

since Nauty can't yet handle multi-graphs, let's transform a multigraph  G
into a digraph G'.
Let the vertices of G' be the edges of G and there is  an edge
from vertex x to vertex y in G' , iff the target of edge x in  G
equals the source of edge y in G.
Now, is it true that multigraphs G and H are isomorphic,
iff their  derived digraphs G' and H' are isomorphic ?
Given the canonical form of G', how do we transfer it
back into a  canonical multigraph isomorphic to G ?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20040921/d0bd3851/attachment.html 

More information about the Nauty mailing list