On the enumeration of interval graphs
Abstract
We present upper and lower bounds for the number of interval graphs on vertices. Answering a question posed by Hanlon, we show that the ordinary generating function for the number of interval graphs has radius of convergence zero. We also show that the exponential generating function -vertex has radius of convergence at least .
1. Introduction
An undirected graph is an interval graph if there is a one-to-one correspondence between its vertices and a set of intervals of the real numbers such that two vertices are adjacent if and only if their corresponding intervals overlap (that is, have a non-empty intersection). The concept of an interval graph appears first to have been formulated in 1957 by Hajós Reference 2, who posed the problem of determining whether a given graph is an interval graph. In 1959, the biologist Benzer Reference 1 independently reformulated the problem in connection with the question of whether the observed overlaps among gene fragments were compatible with the hypothesis that the structure of the gene is linear. The first intrinsic characterization of interval graphs was given in 1962 by Lekkerkerker and Boland Reference 4, who showed that a graph is an interval graph if and only if it is chordal (that is, every cycle of length at least four has a chord) and anasteroidal (that is, among every three vertices, there is one that is adjacent to every path between the other two). They also gave a characterization in terms of an infinite family of forbidden induced subgraphs.
In 1982, Hanlon Reference 3 addressed the problem of enumerating interval graphs (that is, determining the number of (isomorphism classes of) interval graphs with vertices). He solved this problem by giving a system of equations defining a set of formal power series including the (ordinary) generating function for interval graphs. This implicit enumeration allowed him to tabulate for up to ( has decimal digits), but it did not give an explicit formula for or even allow determination of its asymptotic behavior. Indeed, Hanlon posed the question of whether the radius of convergence of is positive (that is, whether is eventually bounded by for some constant (In Hanlon’s tabulation, the entry ). is missing, and the entry is erroneously given as The correct values are given as sequence A005975 by Sloane .Reference 5.)
In Section 2, we shall give a lower bound to that grows “factorially” and therefore shows that the radius of convergence of is zero. In Section 3, we shall give an upper bound to that shows that the exponential generating function has a radius of convergence that is at least .
2. Lower bound
In this section, we shall prove the lower bound
Since is non-decreasing, (2.1) implies that the coefficients in the formal power series are bounded below by those of Since this last power series has radius of convergence zero, so does . thus answering Hanlon’s question. ,
To prove (2.1), we shall associate with each permutation of the set a -colored interval graph -vertex This association will be one-to-one (that is, the permutation . can be recovered from the colored graph Since there are only ). distinct -colored interval graphs, we have -vertex which is equivalent to (2.1). ,
Let be a permutation of We shall construct . intervals, with endpoints First we construct . red intervals, for Then we construct . blue intervals, for Finally, we construct . white intervals, for Let . be the interval graph whose colored vertices correspond to the colored intervals just constructed. It remains to show that the permutation can be recovered from the colored graph Let us define the red degree . of a white vertex to be the number of red vertices adjacent to and the blue degree to be the number of blue vertices adjacent to The interval . intersects and The corresponding vertex . thus has and Thus, . which shows that , can be recovered from .
It is clear that (2.1) could be improved slightly by using only red and blue intervals, for example, and by using a sharper upper bound to the number of colorings used. But we have not pursued these improvements, as none of them improve the factor in the relation between and .
3. Upper bound
In this section, we shall prove the upper bound
where We have . The last inequality yields .
which implies, because the coefficients of are non-negative, that the radius of convergence of is at least It remains an open question to determine if . has a larger radius of convergence or is perhaps even an entire function.
To prove (3.1), we observe that the endpoints of the intervals in the representation of an interval graph can, without loss of generality, be taken to be the -vertex positive integers The . intervals then correspond to a partition of these integers into blocks, each containing two integers that are the endpoints of an interval. This partition can be specified by first choosing the mate of from among the integers (which can be done in ways), then choosing the mate of the smallest as-yet-unpaired integer from among the greater as-yet-unpaired integers (which can be done in ways), and continuing in this way until all integers have been partitioned into mated pairs. This can thus be done in ways. Since every interval graph corresponds to at least one partition, we have established (3.1).
4. Conclusion
In view of Stirling’s formula, one way of roughly stating our results is
It remains an open problem to bring the coefficients and in the lower and upper bounds closer together, perhaps even to obtain an estimate of the form
for some constant .