Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

4 Answers 4

up vote 4 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|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

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|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

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|improve this answer

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|improve this answer

Your Answer

 
discard

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.