1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ You are right, but that is a description of the structure of $G$, independent of the edge orientation. $\endgroup$ – LukasB97 Mar 22 at 16:18
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.