Maximum cliques of the transitive closure of a chordal DAG

directed graphsdiscrete mathematicsgraph theory

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'$?

Best Answer

Consider the following graph, with edges oriented from left to right : Graph

This graph is chordal.

The transitive closure of this graph is the complete graph without every vertical edges.

A clique in the transitive closure is any subset of the vertices such that there isn't two vertices with the same $x$ coordinate.

A maximal clique is thus a maximal set of such vertices, so one for each different $x$ coordinate.

There is an exponential number of those : $2^{\frac {n-1} 3}$.

This construction isn't optimal, but I guess this lower bound gives the idea.

Related Question