[Nauty] Schreir Sims Representation

[Bulutoglu Dursun A Civ AFIT/ENC]

	I was also wondering if there is a way I could get a set of
strong generators from Nauty for a prespecified base. I understand this
may be inefficient for longer bases but I need this for a specific
application.
	Dursun.


It suffices to have a base such that the stabiliser of the whole base is
the identity.  There is no need to expand it to include every vertex and
this would only create inefficiencies.

If you want to generate the full group element by element, you can use
procedures in the nauty package.  The main file is naugroup.c.
To use it, follow the example given in the file nautyex3.c.  The cost of
making the whole group from the generators is slightly more than one
permutation multiplication per element.  Eventually there will be proper
documentation for this facility; for now the comments in nautyex3.c and
naugroup.c are the best there is.  In addition to the procedure
allgroup() used in nautyex3.c, there is allgroup2() that allows you to
abort the generation of the group at any point.

Brendan.


* Bulutoglu Dursun A Civ AFIT/ENC <Dursun.Bulutoglu at afit.edu> [040718
12:50]:
> 	Nauty gives a set of strong generators for the automorphism
group of 
> a graph based on a base v_0, v_2,...v_{k-1}. I was wondering if it is 
> possible to get a set of strong generators for the automorphism group 
> based on a base v_0,v_1, v_2, ...v_{n-1}  ie a base that uses all the 
> vertices of the graph. This would give me an efficient way of 
> generating the group. Since then every element of the group can be 
> written uniquely as a product of strong generators. This is not the 
> case when the base is a strict subset of the n vertices. If this is 
> possible is the running time of the algorithm going to be effected 
> from such a change. The set of strong generators based on all the 
> vertices can be generated by using the strong generators based on a 
> subset of all the vertices. The question is whether it would be more 
> efficient to get the strong generators based on all the vertices
directly from nauty.
> 	Dursun.

_______________________________________________
This is the nauty mailing list
Post messages to nauty-list at cs.anu.edu.au nauty page:
http://cs.anu.edu.au/~bdm/nauty/ list page:
http://cs.anu.edu.au/mailman/listinfo/nauty-list