MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A cograph is a graph without induced $P_4$ subgraphs. I am looking for a reference for a simple exponential bound on the number of distinct unlabeled cographs on $n$ vertices. By the Mathworld article on cographs this is the same as the number of series-parallel networks with $n$ unlabeled edges. Judging from the first couple of terms in the list, the bound should be something like $3^n$. Any reference to a simple, exponential bound in closed-form would be much appreciated.

share|cite|improve this question
up vote 5 down vote accepted

Let your sequence be $a_n$ for the number of series-parallel networks with $n$ unlabeled edges. The following identity of generating functions holds $$1+\sum_{k=1}^{\infty}a_kx^k=\left[\frac{1}{(1-x)}\prod_{k\geq 1}\frac{1}{(1-x^k)^{a_k}}\right]^{1/2}$$ from which the asymptotics $$a_n\sim C d^n n^{-3/2}$$ follow, where $C=0.4126...$, $d=3.56083930953894...$

See also the article "Some enumerative results on series parallel networks" by J.W. Moon.

share|cite|improve this answer
Thanks, this seems to be the number I'm looking for! I'll have a look in the paper to see whether I can distill the same information. – Bart Jansen Sep 7 '10 at 11:15

See e.g. the Wikipedia article on cographs, which explains that isomorphism classes of cographs are in one-to-one correspondence with isomorphism classes of n-leaf rooted trees in which the internal nodes are labeled with 0's and 1's and in which, moreover, the labels are in strict alternation from root to leaf.

Because of the alternation, the labeling part only adds a factor of two to the overall count, so really all you need to do is to count n-leaf rooted trees. So the number of cographs appear to be the numbers in OEIS sequence A000084 (the number of trees is half that, A000669). They are asymptotic to around 3.561^n, matching Zaimi's answer.

share|cite|improve this answer

A cograph on $n$ vertices can be created by starting with $n$ 1-vertex graphs and then going through a procedure of at each turn either (1) complementing a graph, or (2) replacing two of your graphs with their disjoint union, and stopping when you have one graph remaining.

The number of ways that (2) can be done is the $n$th Catalan number, and at each stage you have the option of complementing.

I think this should give a $O(8^n)$ bound.

share|cite|improve this answer
Since Catalan numbers grow like $4^n$, your final estimate is too low (maybe should be $8^n$?), but I like the basic idea. – JBL Sep 6 '10 at 15:17
@JBL, thanks - I've corrected it. – Emil Sep 6 '10 at 15:33

The paper "Enumeration and limit laws of series-parallel graphs" by Manuel Bodirsky, Omer Gimenez, Mihyun Kang, and Marc Noy, establishes that the number of labeled series-parallel graphs on $n$ vertices is asymptotically $$ g \cdot n^{-\frac{5}{2}} \gamma^n n! $$ where $g$ and $\gamma$ are constants. Perhaps you can convert their bound to one for unlabeled graphs (by removing the $n!$ factor) in terms of edges.

share|cite|improve this answer
This is tricker: you cannot remove directly the n! factor. The constant gamma also changes. – gaussian-matter Jan 18 at 19:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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