New answers tagged


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