[Nauty] Multigraphs..

Gordon Royle gordon at csse.uwa.edu.au
Wed Sep 22 14:13:02 EST 2004

I have had some success with one of two approaches for multigraphs

(1) Subdivide each multiple edge

	- if there are few multiple edges or they have low multiplicity, then 
this will not cause the size to blow out too much
	- if you have "real" vertices of degree 2 floating around, then you 
will have to use the lab/ptn facility to put all added vertices into a 
single class to avoid then getting mixed up with real vertices


(2) Assign one new vertex for each different possible multiplicity, and 
if an edge is joined by k edges, join both its ends to the new vertex 
representing "k".

	- use lab/ptn to put each new vertex into its own cell to stop them 
getting permuted (eg swapping all double-edges with triple-edges)
	- if there are few different multiplicities then this will cause only 
a small increase in graph size

More information about the Nauty mailing list