[GAP Forum] a graph question

[Leonard Soicher]

Dear Petra, Dear GAP Forum,

>> 
>> On Tue, Jun 15, 2004 at 12:48:07PM +0100, Petra Holmes wrote:
>> > I have a graph on about 25000 points.  I would like to find the size of a
>> > maximal set of pairwise non-adjacent points.  Is there a way to do this in
>> > GAP?
>> > 

First, let's take the complement  gamma  of your graph, so what we are 
looking for is a certain complete subgraph. 

As Steve Linton said, the GAP Package GRAPE has functions to determine
certain sets of complete subgraphs of a (possibly vertex-weighted)
graph, subject to user specified parameters.  See the documentation for
the GRAPE functions  CompleteSubgraphs  and
CompleteSubgraphsOfGivenSize.

Now if what you really want is a maximal complete subgraph (i.e. one
which is not properly contained in a larger complete subgraph of gamma) then
this is easy: just call  CompleteSubgraphs(gamma,-1,0) .  However, I
suspect you are interested in the much harder problem of finding the
maximum size of a complete subgraph of gamma.  Here,
CompleteSubgraphsOfGiven  may help.  As Steve said, this depends
very much on the graph gamma and a known subgroup of its automorphism
group (it may be possible to compute Aut(gamma) via GRAPE and
nauty).  Then (after constructing gamma in GRAPE using the known
subgroup of Aut(gamma)) the call
CompleteSubgraphsOfGivenSize(gamma,k,0,true) can be used to determine
whether  gamma  contains a maximal complete subgraph of size k. So
what you want to find is the largest  k  for which this is true.

I would be very happy to give you further advice (outside of the 
Forum) if you send me details about your graph.

Best wishes,  Leonard