[Nauty] multigraphs

[Brendan McKay]

* Sterten at aol.com <Sterten at aol.com> [040921 16:25]:
> 
> 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 ?

No.  Consider the case where G consists of a few directed edges with
the same source and different targets.  G' has no edges at all if I
understand your definition.

Your construction is one of the serveral things called the line digraph
and there is literature on it.  I don't know what the answer is if
G is constrained to be strongly connected, but I'm sure it is known.

The next version of nauty has a generator for undirected multigraphs.
It is written and appears to work but needs further testing before
release.

Brendan.