[Nauty-list] status of generator for undirected multigraphs?

[Brendan McKay]

* Michael Kiermaier <michael.kiermaier at uni-bayreuth.de> [061130 08:54]:
> > [...]
> > That's it.  Note that x=0 and y=0 are forbidden.  This rule can
> > be relaxed slightly, but care is needed.  It is important that for any
> > vertex z[0,j], the vertices z[1,j],...,z[k-1,j] are combinatorially
> > determined, which is not always true if x=0 and y=0 are allowed without
> > restriction.
> 
> Thanks for the explanation, I think I got it.
> 
> To make this method work, it is necessary that for all j and all 1<=i<=k
> there is an edge (z[0,j],z[i,j]).
> Thats the reason why the "path" layer-connection type does not work any
> more and why "star" has its center in layer 0, right?
> 
> ~michael

The important thing is that the n vertical sets
   { z[0,j], z[1,j],...,z[k-1,j] }
for each j cannot be mixed up with each other by automorphisms.
That is, the image of a vertical set under an automorphism must
be a vertical set (not necessarily the same one).  This is easy
to achieve using the clique or star method, but with the path
method it is plausible that the vertical path might be mapped
by an automorphism onto a non-vertical path. 

Brendan.