[GAP Forum] a graph question
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