[Nauty-list] digraph-->graph

[Sterten at aol.com]

ok, I think this should work:
 
--------------------------------------------------
add vertices d1,d2,d3,d4,d5,{a',a in V},{a'',a in V}
and edges (d1,d2),(d3,d4),(d4,d5),(d2,a),(d5,a')(a',a''),(a,a'') 
and edges (a,b')for (a,b) in E, but remove (a,b) for (a,b) in E
 
 
exactly two vertices have degree 1 : d1 and d3, their neighbors are  d2,d4.
d2 has degree > 2 except for trivially small graphs.
d4 has degree 2
The neighbors of d2 are the a (incoming) the neighbors of d4 are the a'  
(outgoing)
the other vertices are the a'' that have degree 2 and join the a with the  
a'
------------------------------------------------------------
 
 
I first tried it with taking the edges as vertices and joining them to  
their endpoints,
but probably had insufficiently distinguished them so I got  
1,3,7,19,47,128,...
instead of 1,3,7,19,47,130,... (using nauty for graphs, not digraphs)
 
 
 

 
 
In a message dated 19.10.2013 18:31:01 Westeuropäische Sommerzeit,  
mathieu.dutour at gmail.com writes:

One way is to duplicate the number of vertices.  
Any vertex a is associated to a pair a, a'.


A directed edge a ---> b becomes an undirected
edge {a, b'}.
We associate color 0 to all vertices x and color 1
to all vertices x'.


Mathieu



On Sat, Oct 19, 2013 at 5:53 PM, <_Sterten at aol.com_ 
(mailto:Sterten at aol.com) > wrote:


how did we best make a graph from a digraph with isomorphic  automorphism 
group  ?


_______________________________________________
Nauty-list  mailing list
_Nauty-list at cs.anu.edu.au_ (mailto:Nauty-list at cs.anu.edu.au) 
http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list






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