[Nauty] multigraphs

[Sterten at aol.com]

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
release.

Brendan.




------------------------------------
 
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 
new
sink(source) ?
The typical way I would "prove" such things would be empirically testing  it
with Nauty...
 
Guenter.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20040921/f9788da9/attachment.html