[GAP Forum] GRAPE: maximal cliques of given size?

Leonard Soicher L.H.Soicher at qmul.ac.uk
Fri Apr 26 09:29:36 BST 2013


Dear Frédéric, Dear GAP-Forum,

First, make sure you have the latest version of GRAPE (4.6), and read the
documentation for the very flexible function CompleteSubgraphsOfGivenSize
(you should also review the documentation for CompleteSubgraphs
(a.k.a. Cliques)).

In particular:

        CompleteSubgraphsOfGivenSize( gamma, k, 2, true ); 

will return a set of  gamma.group  orbit-representatives of the maximal
cliques of size  k  of the simple graph  gamma.  If you want to classify
the maximal cliques of size  k  up to the action of the automorphism
group of  gamma,  then you must first make sure that gamma.group  is that
(full) automorphism group.  This can be accomplished via:

       gamma := NewGroupGraph( AutomorphismGroup(gamma), gamma ); 

Best wishes,
Leonard

On Fri, Apr 26, 2013 at 08:34:38AM +0200, Frederic Vanhove wrote:
> Dear members of the forum,
> 
> I have a question on cliques in GAP, and on the package GRAPE in particular.
> I would like to obtain all maximal cliques (up to isomorphism) of a 
> given size k in a graph.
> 
> CompleteSubgraphsOfGivenSize(graph,k,true);
> will give me representatives (maybe isomorphic ones) of cliques of size k
> 
> Cliques(graph, -1,2);
> will give me representatives (maybe isomorphic ones) of maximal cliques 
> of any size
> 
> But is there any (efficient) way to obtain the maximal cliques of one 
> fixed size k (I am hoping this would be faster than Cliques(graph,-1,2))
> 
> Thanks,
> Kind regards,
> Frédéric
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum



More information about the Forum mailing list