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 seriesparallel 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 closedform would be much appreciated.
Let your sequence be $a_n$ for the number of seriesparallel networks with $n$ unlabeled edges. The following identity of generating functions holds $$1+\sum_{k=1}^{\infty}a_kx^k=\left[\frac{1}{(1x)}\prod_{k\geq 1}\frac{1}{(1x^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.

$\begingroup$ 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. $\endgroup$ – 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 onetoone correspondence with isomorphism classes of nleaf 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 nleaf 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.
A cograph on $n$ vertices can be created by starting with $n$ 1vertex 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.

$\begingroup$ Since Catalan numbers grow like $4^n$, your final estimate is too low (maybe should be $8^n$?), but I like the basic idea. $\endgroup$ – JBL Sep 6 '10 at 15:17
The paper "Enumeration and limit laws of seriesparallel graphs" by Manuel Bodirsky, Omer Gimenez, Mihyun Kang, and Marc Noy, establishes that the number of labeled seriesparallel 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.

1$\begingroup$ This is tricker: you cannot remove directly the n! factor. The constant gamma also changes. $\endgroup$ – gaussianmatter Jan 18 '16 at 19:21