Dear Gap Forum,

Chris Charnes recently asked:

I would like to know (refrence?) what algorithms
GRAPE uses to find complete subgraphs with side conditions of a given graph.

At present the only reference for the GRAPE functions
'CompleteSubgraphs' and 'CompleteSubgraphsOfGivenSize' is the GAP
manual and the GRAPE library source code. Of the two functions,
'CompleteSubgraphsOfGivenSize' is the more sophisticated, and should be
used if at all possible.

I'm not sure what you mean by 'side conditions of a given graph'.
'CompleteSubgraphsOfGivenSize' finds complete subgraphs of a given size
(surprise surprise), and is controlled in its search and output by the
parameters as documented. 'CompleteSubgraphs' can also be used to
find complete subgraphs of a given size (but is not as good as
'CompleteSubgraphsOfGivenSize') or to find maximal complete subgraphs.
Again, you should read the documentation to see how to control this
(less sophisticated) function.

I am developing a new version of 'CompleteSubgraphsOfGivenSize'
which has the following features:

(1) It allows you to assign integer weights to the vertices
of the input graph, gamma (the weight of a vertex must be
preserved by gamma.group) and then the *size* of a complete
subgraph (to be found) is the sum of the weights of its vertices.
Thus, the new version does the same as the old when each vertex
has weight 1 (the default).

(2) It has more thorough documentation than the old version.

(3) It is slightly easier to control.

If you would like a copy of this new (experimental) version,
then I would be happy to send it to you, but would like to
be informed how things go with it. Eventually, I plan
to write a paper on the ideas and algorithms behind this
new function.

Best regards, Leonard.