# 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. – LukasB97 Mar 22 at 16:18

## 1 Answer

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.