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

<p>See <a href="https://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices">https://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices</a>.</p>

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

CC BY-SA 3.0
2015-10-08T13:58:17.273Z
2015-10-08T13:58:17.273Z
2017-04-13T12:57:54.777Z
shahin kamali
<p>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. </p>

<p>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})$. </p>

CC BY-SA 3.0
2015-10-09T08:13:38.240Z
2015-10-09T08:13:38.240Z
M. kanté
<p>The <a href="http://en.wikipedia.org/wiki/Clique-width" rel="nofollow">clique-width</a> 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))).$$</p>

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

CC BY-SA 3.0
2015-10-08T16:39:58.060Z
Is your question asking how many graphs have clique width $k$, or how many $k$-expressions generate an input graph? (In the latter case, useless renames clearly make the number infinite; are you bounding the expression size, or forbidding useless renames somehow?)
Antoine Amarilli 'a3nm'
<graph-theory><graph-algorithms><treewidth><cliquewidth>
Number of k-expressions of graph (clique Width)
GOLD
# Number of k-expressions of graph (clique Width)

(Asked by: username_0 on 2014-12-04)

The [clique-width](http://en.wikipedia.org/wiki/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?

**Tags:** graph-theory, graph-algorithms, treewidth, cliquewidth

> **Comments:**
> **username_1**: Is your question asking how many graphs have clique width $k$, or how many $k$-expressions generate an input graph? (In the latter case, useless renames clearly make the number infinite; are you bounding the expression size, or forbidding useless renames somehow?)  

---

## 2 answers

### Answer by username_2 on 2015-10-08. Score: 2

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 by username_3 on 2015-10-09. Score: 0

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


---

