Consider a saturated chain $G_0 \subset G_1 \subset \cdots \subset G_m$ of graphs on $n$ labelled vertices, where $G_i$ has $i$ edges, and $m = {{n}\choose {2}}$. Altogether there are $m!$ such chains of graphs (they are also known as "graph processes") and they form an interesting topic of study.

Recall that $G$ is chordal if all induced cycles in $G$ are 3-gons.

## The question

Let $f(n)$ be the number of such chains where all graphs $G_i$ are chordal. What is the value of $f(n)$? a) for small values of $n$? b) what is its asymptotic behaviour? c) Is there an exact formula?

Of course $f(n) \le {{n} \choose {2}}!$, and it is easy to see that $f(n) \ge \prod_{k=1}^{n-1} k!$.

Variations: We can also ask about a) saturated chains of perfect graphs, b) saturated chains of chordal graphs whose complement is also chordal.

## Motivation

For a saturated chain of graphs $G_0 \subset G_1 \subset \cdots \subset G_m$ we can look at the vector $(v_0,v_1,...,v_{n-1})$ where $v_k$ is the number of indices $j$ where $G_{j+1}$ has $k$ additional triangles compared to $G_j$. Such vectors introduced by Beus in 1970 (in the context of sorting algorithms) are interesting parameters of saturated chains of graphs and the case of chordal graphs is precisely the case where the vector is $(n-1,n-2,\dots,1)$.

### Remark:

$f(3)=6$, and $f(4)=576$. I am curious to know the values of $f(5)$ and $f(6)$.

8more comments