4
$\begingroup$

Say we have a graph:

g = CompleteGraph[5];

and that we want to find all the triangles in g. I tried to use FindKClique, in the following way:

FindKClique[g,1,{3},All]

but it returns an empty list and I am not sure why. I must be misunderstanding something about FindKClique but I'm not sure what it is. The output I would expect to get is the following:

Map[First,FindCycle[g,{3},All],{2}]

{{3, 2, 4}, {3, 5, 4}, {1, 5, 3}, {2, 3, 5}, {2, 4, 5}, {1, 5, 2}, {1, 3, 2}, {1, 2, 4}, {1, 3, 4}, {1, 5, 4}}

Can someone explain why FindKClique is not doing what I thought it would?

$\endgroup$
6
$\begingroup$

From the docs of FindKClique,

A k-clique is a maximal set of vertices that are at a distance no greater than k from each other.

There are no maximal cliques that are 3-cliques in $K_5$.

I suggest you use IGCliques from IGraph/M, which finds all cliques, not just maximal ones.

<< IGraphM`

IGCliques[CompleteGraph[5], {3}]
(* {{3, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}} *)

If you only need triangles (not larger cliques), you can also use IGTriangles, which is going to be faster.

IGTriangles[CompleteGraph[5]]
(* {{1, 2, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {1, 3, 4}, {1, 4, 5}, {2, 3, 5}, {2, 3, 4}, {2, 4, 5}, {3, 4, 5}} *)

If you need to find sets of vertices no more than distance $k$ away, as with FindKClique, first connect each vertex to its $k$-neighbourhood, then find normal cliques.

IGCliques[IGConnectNeighborhood[graph, k], {size}]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.