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

[Gunnar Brinkmann]

> 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.


@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.


						Gunnar