[Nauty] Multigraphs

[Stephan Winkler]

Hi,

 

Is there a possibility to compute canonical labellings for multigraphs 

(graphs with multiple edges between pairs of vertices) using nauty? If 

this cannot be done directly, as suggested by the documentation, are 

there ways to encode multigraphs appropriately by [coloured] simple 

graphs, which may then be analyzed using nauty?

 

For example, if there are n > 1 edges between two vertices x and y, we 

could model this by a single edge annotated by n. Can we represent 

this in nauty by introducing a new vertex between x and y and 

assigning it colour n?

 

Will future versions of nauty handle multigraphs? Are there any other 

software packages available that efficiently compute canonical 

labellings for multigraphs? Any help is greatly appreciated,

 

Stephan Winkler.

 

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