[GAP Forum] a graph question

Leonard Soicher l.h.soicher at qmul.ac.uk
Wed Jun 16 16:25:21 BST 2004

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

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

More information about the Forum mailing list