Number of k-expressions of graph (clique Width)

Question

The clique-width of a graph $G$ is the minimum number of labels needed to construct G by means of the following 4 operations. The Construction of a graph $G$ using the four operations is represented by an algebraic expression called $k$-$expression$, Where $k$ is the number of labels used in expression. For example, $K_4$(complete graph with four vertices) can be constructed by $$\rho_{2\rightarrow 1}(\eta_{1,2}(\rho_{2\rightarrow 1}(\eta_{1,2}(\rho_{2\rightarrow 1}(\eta_{1,2}(a(1)\oplus b(2)))\oplus c(2))) \oplus d(2))).$$

Question--> How many k-expressions for bounded clique width graph? Any particular graph classes known for this question?

Answer 1

Cographs have clique width 2, and the number of cographs of size $n$ is asymptotically equal to $3.56^n$.

See https://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices.

I am not sure how many graphs with a given clique-width $k$ exist.

Answer 2

you can asymptotically have something like that (I count several times isomorsphic copies) : A k-expression can be constructed from a binary tree as follows: insert between two nodes unary operations.

For k fixed the number of possible unary operations is bounded by $k^k$ (you avoid repetitions: add first edges, and then rename). Since the number of adding operations is k(k-1)/2 and the number of renaming is the number of functions from [k] to [k], you have the bound of $2^{k^2}\times k^k$. So, since the number of binary trees with $n$ leaves is counted by catalan numbers $C_{n-1}$, you have the upper bound $O(2^{k^2}\times C_{n-1})$.