bdm at cs.anu.edu.au
Tue Sep 21 17:06:01 EST 2004
* 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
More information about the Nauty