[Nauty] multigraphs

Sterten at aol.com Sterten at aol.com
Tue Sep 21 17:28:02 EST 2004

In einer eMail vom 21.09.2004 09:06:17 Westeuropäische Sommerzeit schreibt  
bdm at cs.anu.edu.au:

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


thanks, I'll search for line digraphs.
We had it for DAGs with one source and one sink and it seems to work  fine, 
so I just thought it could maybe be generalized.
What, if we first connect all vertices of G with out(in)degree zero with  one 
sink(source) ?
The typical way I would "prove" such things would be empirically testing  it
with Nauty...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20040921/f9788da9/attachment.html 

More information about the Nauty mailing list