# Maximum cliques of the transitive closure of a chordal DAG

Let $$G=(V,A)$$ be a directed acyclic graph, for which the underlying undirected graph is chordal (so that every induced cycle in the underlying undirected graph is a triangle).

It is known that in a chordal graph the number of maximum cliques is linearly bounded in the number $$|V|$$ of vertices.

Let $$G'=(V,A')$$ be the transitive closure of $$G$$, so that for every directed path $$p= (v_i,\ldots,v_j)$$ from $$v_i$$ to $$v_j$$ in $$G$$, there exists a directed edge $$(v_i,v_j)$$ in $$A'$$.

Question: Is there any polynomial/linear bound on the number of maximum cliques in the undirected graph that underlies $$G'$$?

• You are right, but that is a description of the structure of $G$, independent of the edge orientation. Mar 22 at 16:18

I think you can extend Vinicius dos Santos' idea to show that no polynomial bound is possible.

Consider a graph on $$n$$ vertices divided into $$d\geq 1$$ groups of size about $$n/d$$ as follows: Its transitive closure has about $$(\frac{n}{d})^d$$ maximal (undirected) cliques.

• @Laakeri Then I must have my definitions mixed up somehow, it seems chordal to me :/ May 20 at 8:58
• I'm sorry, of course it's a chordal graph. Somehow I didn't see the edge in the middle. May 20 at 9:15
• @Laakeri All good! May 20 at 18:08

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 maximum) cliques.