<p>I think you can extend Vinicius dos Santos' idea to show that no polynomial bound is possible.</p>
<p>Consider a graph on <span class="math-container">$n$</span> vertices divided into <span class="math-container">$d\geq 1$</span> groups of size about <span class="math-container">$n/d$</span> as follows:</p>
<p><a href="https://i.sstatic.net/ANLX8.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ANLX8.png" alt="enter image description here" /></a></p>
<p>Its transitive closure has about <span class="math-container">$(\frac{n}{d})^d$</span> maximal (undirected) cliques.</p>

CC BY-SA 4.0
2021-05-20T08:58:30.737Z
@Laakeri Then I must have my definitions mixed up somehow, it seems chordal to me :/
Tassle
CC BY-SA 4.0
2021-05-20T09:15:36.183Z
I'm sorry, of course it's a chordal graph. Somehow I didn't see the edge in the middle.
Laakeri
CC BY-SA 4.0
2021-05-20T18:08:22.680Z
@Laakeri All good!
Tassle
CC BY-SA 4.0
2021-05-19T21:04:22.180Z
2021-05-19T21:04:22.180Z
Tassle
<p>A linear bound is impossible. Suppose your graph is a star, with half of the edges oriented towards the universal vertex <span class="math-container">$u$</span> and the rest oriented outward. In the transitive closure, the maximal cliques will be triangles, each of them containing <span class="math-container">$u$</span> and exactly one of its inneighbors and one of its outneighbors. This gives a quadratic number of maximal (and maximum) cliques.</p>

CC BY-SA 4.0
2021-04-19T19:46:40.477Z
2021-04-19T19:46:40.477Z
Vinicius dos Santos
<p>Let <span class="math-container">$G=(V,A)$</span> 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).</p>
<p>It is known that in a chordal graph the number of <em>maximum cliques</em>
is linearly bounded in the number <span class="math-container">$|V|$</span> of vertices.</p>
<p>Let <span class="math-container">$G'=(V,A')$</span> be the transitive closure of <span class="math-container">$G$</span>, so that for
every directed path <span class="math-container">$p= (v_i,\ldots,v_j)$</span> from <span class="math-container">$v_i$</span> to <span class="math-container">$v_j$</span>
in <span class="math-container">$G$</span>, there exists a directed edge <span class="math-container">$(v_i,v_j)$</span> in <span class="math-container">$A'$</span>.</p>
<blockquote>
<p><strong>Question:</strong> Is there any polynomial/linear bound on the number
of maximum cliques in the undirected graph that underlies <span class="math-container">$G'$</span>?</p>
</blockquote>

CC BY-SA 4.0
2021-03-22T16:18:07.083Z
You are right, but that is a description of the structure of $G$, independent of the edge orientation.
LukasB97
<graph-theory><graph-algorithms><clique><transitive-closure>
Maximum cliques of the transitive closure of a chordal DAG
LukasB97
# Maximum cliques of the transitive closure of a chordal DAG

(Asked by: username_0 on 2021-03-22)

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

**Tags:** graph-theory, graph-algorithms, clique, transitive-closure

> **Comments:**
> **username_0**: You are right, but that is a description of the structure of $G$, independent of the edge orientation.  

---

## 2 answers

### Answer by username_1 on 2021-05-19. Score: 4

I think you can extend username_3' 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:

[![enter image description here](https://i.sstatic.net/ANLX8.png)](https://i.sstatic.net/ANLX8.png)

Its transitive closure has about $(\frac{n}{d})^d$ maximal (undirected) cliques.

> **Comments:**
> **username_1**: @username_2 Then I must have my definitions mixed up somehow, it seems chordal to me :/  
> **username_2**: I'm sorry, of course it's a chordal graph. Somehow I didn't see the edge in the middle.  
> **username_1**: @username_2 All good!  

---

### Answer by username_3 on 2021-04-19. Score: 1

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.


---

