[GAP Forum] Independent sets/complete subgraphs in GRAPE

[Leonard Soicher]

Dear Reza Orfi, Dear GAP-Forum,

Let gamma be a simple graph, and delta the complement graph of gamma.
Then X is an independent set of gamma if and only if X is a clique of
delta (that is, the subgraph induced on X is a complete graph). 

Thus, finding and classifying independent sets in gamma is equivalent
to finding and classifying complete subgraphs of delta, and for this you
can use the functions CompleteSubgraphs and CompleteSubgraphsOfGivenSize
in GRAPE.  Please read their documentation carefully. 

Note that a *maximal* complete subgraph K of delta is one which is not
properly contained in another complete subgraph of delta, although there
may be complete subgraphs of delta larger than K.  Should you wish to
find a *maximum* complete subgraph of delta (that is, one of maximum
size, and corresponding to a maximum independent set of gamma), then
you could apply the function CompleteSubgraphsOfGivenSize (and binary
search) to find the largest k such that delta has a complete subgraph
of size k. 

Before any searching for any complete subgraphs of delta it is usually
a good idea to make sure that delta.group is the full automorphism group
of delta. This can be done by the statement:

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

To determine whether delta has a complete subgraph of size k, and to
produce one if so, the function call would be:

CompleteSubgraphsOfGivenSize(delta,k,0); 

Now suppose m is the size of a maximum complete subgraph of delta. Then
in particular, all complete subgraphs of delta of size m are maximal,
so you could classify the maximum complete subgraphs of delta, up to
the action of delta.group, using the function call:

CompleteSubgraphsOfGivenSize(delta,m,2,true); 

Hope all this is helpful,
Leonard Soicher

On Tue, Jun 14, 2011 at 07:37:06AM -0700, Reza Orfi wrote:
> Dear Prof.  Leonard Soicher
> I have a question .
> Is there any way to commpute the maximal independent sets
> in GAP ?
> There is a function in GRAPE to commpue independent set ( IndependentSet(gamma)).
> But this function return a (hopefully large) independent set of the graph gamma.
>  
> Best regards
>         Reza Orfi
>  
>  
> --- On Mon, 6/13/11, Leonard Soicher <L.H.Soicher at qmul.ac.uk> wrote:
> 
> 
> From: Leonard Soicher <L.H.Soicher at qmul.ac.uk>
> Subject: [GAP Forum] On GRAPE for GAP 4.5/removal of old functions
> To: forum at gap-system.org
> Date: Monday, June 13, 2011, 4:58 AM
> 
> 
> Dear GAP-Forum,
> 
> I am preparing a new version of GRAPE which will (hopefully) be finished
> in time for release with GAP 4.5. One major step (forward?) should be
> the ability to interface with nauty on a computer running Windows. This
> has been made possible due to the hard work of Alexander Hulpke.
> 
> In addition, I'd like to remove some old undocumented functionality
> requiring external binaries (this functionality is now largely provided
> by inbuilt GAP/GRAPE functions). Please let me know at once if you use
> either of the functions Enum  or EnumColadj in GRAPE, as I plan to remove
> these functions, and their associated external programs from the next
> release of GRAPE.
> 
> Regards,
> Leonard Soicher
> 
> 
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum