New answers tagged clique
0
A linear bound is impossible. Suppose your graph is a star, with half of the edges oriented towards the universal vertex $u$ and the rest oriented outward. In the transitive closure, the maximal cliques will be triangles, each of them containing $u$ and exactly one of its inneighbors and one of its outneighbors. This gives a quadratic number of maximal (and ...
Top 50 recent answers are included
