The number of chains of chordal graphs

Question

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)$.

Answer 1

This is not a general answer but the big numbers don't fit properly into a comment.

f(1) = 1
f(2) = 1
f(3) = 6
f(4) = 576
f(5) = 1416960
f(6) = 120678543360
f(7) = 455010170456862720
f(8) = 95371866538619173904056320
f(9) = 1383866987105877308750365304858542080
f(10) = 1716187027583005555045945024371317843956845772800
f(11) = 221917018834976627508152930913765491170568412125060985539788800
f(12) = 3598055237740601485367382153175891099609454479883844294426214728495086488780800
f(13) = 8665460290021468438320782226358244848272843476236433280013965605190231652374443764439998581964800

The last two took about 10 minutes and 5 hours.

For a graph $G$ let $g(G)$ be 0 if $G$ is not chordal and equal to the number of chordal chains back to the empty graph otherwise.

Set $g({\rm empty})=1$ and for one member $G$ of each isomorphism class of nonempty chordal graph in non-decreasing order of the number of edges, do $$ g(G) := \sum_{e\in E(G)} g(G-e). $$ The answer is $g(K_n)$. No adjustment for automorphism group size is needed. The only technical requirement is recognising $G-e$ as isomorphic to a previous graph.

The program can handle any class of graphs closed under isomorphism provided they all fit into memory at once.

On request, here is the corresponding table for split graphs.

s(1) = 1
s(2) = 1
s(3) = 6
s(4) = 480
s(5) = 719040
s(6) = 28111985280
s(7) = 39667596799259520
s(8) = 2716101119587792215121920
s(9) = 11750142295253741381979240922398720
s(10) = 4059370170952132363824590307446791630779187200
s(11) = 138004666315436722628999805261994204164032807656029840998400
s(12) = 557103455087735168484078548670473120844063643381325957791547628642631680000
s(13) = 316753104615638650562235298836069531430557783996203420700809420563227053308369342951115980800
s(14) = 29665849491651526562732309913886504922801500810240504259322068041948739753073885726711112718885233432115281920000