[Nauty] Extending graphs by one vertex

Falk Hueffner falk.hueffner at student.uni-tuebingen.de
Mon Oct 13 22:27:01 EST 2003


Gunnar Brinkmann <gunnar at Mathematik.Uni-Bielefeld.DE> writes:

> > I need to generate from one graph the set of graphs containing one
> > more vertex, with all possible connections to existing vertices. The
> > obvious method is to generate all 2^n possibilities, generate the
> > canonical form for each and filter duplicates. Is there a better way
> > with the nauty library?
> 
> Yes -- MUCH MUCH better -- and there are lots of articles about it
> in the literature.
> 
>   author = 	 {G. Brinkmann},
>   title = 	 {Isomorphism Rejection in Structure Generation Programs},

Thanks for the reference. However, I was hoping there might be some
functionality within nauty itself, or something I could adapt with
little effort, since this is not really that central to my research
and I wouldn't want to spend weeks on it...

-- 
	Falk




More information about the Nauty mailing list