[Nauty] Re: nauty-list digest, Vol 1 #47 - 1 msg

[Sterten at aol.com]

In einer eMail vom 13/10/03 2:05:34 PM (MEZ) - Mitteleurop. Sommerze schreibt 
gunnar at Mathematik.Uni-Bielefeld.DE:


> > Message: 1
> > To: nauty-list at cs.anu.edu.au
> > From: Falk Hueffner <falk.hueffner at student.uni-tuebingen.de>
> > Date: 10 Oct 2003 16:15:01 +0200
> > Subject: [Nauty] Extending graphs by one vertex
> > Reply-To: nauty-list at cs.anu.edu.au
> >
> > Hi,
> >
> > 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? It looks like geng contains something similar,
> > but I'm not sure whether it works with plain graphs or needs
> > additional stored information.
> >
> > --
> >     Falk
> 
> Yes -- MUCH MUCH better -- and there are lots of articles about it in the
> literature.


I'm surprised to hear this. Shouldn't in average all the 2^n graphs be 
different (nonisomorphic) ?
At least asymptotically.


> 
> 
> @InProceedings{B98,
>   author =     {G. Brinkmann},
>   title =     {Isomorphism Rejection in Structure Generation Programs},
>   booktitle =     {Discrete Mathematical Chemistry},
>   pages =     {25--38},
>   year =     {2000},
>   editor =     {P.~Hansen and P.W. Fowler and M. Zheng},
>   volume =     {51},
>   series =     {DIMACS Series on Discrete Mathematics and Theoretical 
> Computer Science},
> publisher = {American Mathematical Society}
> }
> 
> is an easy to read survey article about such methods and contains
> references to other articles in the literature.
> 
> 
>                         Gunna
r


but I'll have to go to Bielefeld to get it ;-)
or is also something available online ?


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