0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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?) $\endgroup$ – a3nm Oct 8 '15 at 16:39
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.