On the Enumeration of Interval Graphs

Abstract

We present upper and lower bounds for the number $i_n$ of interval graphs on $n$ vertices. Answering a question posed by Hanlon, we show that the ordinary generating function $I(x)={\sum }_{n\ge 0}{i}_n{x}^n$ for the number $i_n$ of $n$-vertex interval graphs has radius of convergence zero. We also show that the exponential generating function $J(x)={\sum }_{n\ge 0}{i}_n{x}^n/n!$ has radius of convergence at least $1/2$.

i+3 pp