[Nauty] canonical label for directed graphs

Edward N Turner ent03r at ecs.soton.ac.uk
Tue Aug 23 00:32:23 EST 2005


> You can convert a directed graph into a bipartite undirected graph
with  twice as many vertices and this could be faster for labeling.

Is this correct: would the bipartite undirected graph represent only the
original directed graph? 

e.g., Given a directed graph, call it A, we can convert it into a
bipartite undirected graph, call it X, with twice as many vertices; but
couldn't we then look at X and deduce two directed graphs from it that X
may be representing i.e., the original digraph A, and the digraph
obtained by reversing the direction of each edge in A?

Best, 

Edward.

PS. Apologies - I couldn't find the previous messages regarding
bipartite graphs and directed graphs.









More information about the Nauty mailing list