Bound on the number of unlabeled cographs on n vertices - MathOverflow

Bound on the number of unlabeled cographs on n vertices

2010-09-06T12:17:49Z

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.

Answer by Joseph O'Rourke for Bound on the number of unlabeled cographs on n vertices

2010-09-06T12:35:07Z

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.

Answer by Emil for Bound on the number of unlabeled cographs on n vertices

2010-09-06T13:12:24Z

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.

Answer by Gjergji Zaimi for Bound on the number of unlabeled cographs on n vertices

2010-09-06T13:23:57Z

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.

Answer by David Eppstein for Bound on the number of unlabeled cographs on n vertices

2010-09-06T16:28:42Z

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.