On the enumeration of interval graphs

By Joyce C. Yang and Nicholas Pippenger

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 -vertex interval graphs has radius of convergence zero. We also show that the exponential generating function 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 -vertex interval graph . This association will be one-to-one (that is, the permutation can be recovered from the colored graph ). Since there are only distinct -colored -vertex interval graphs, we have , 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 -vertex interval graph can, without loss of generality, be taken to be the 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 .

References

[1]
S. Benzer, On the topology of the genetic fine structure, Proc. Nat. Acad. Sci. 45 (1959), 1607–1620.
[2]
G. Hajós, Über eine Art von Graphen, Int. Math. Nachr. 11 (1957), 65 pp.
[3]
Phil Hanlon, Counting interval graphs, Trans. Amer. Math. Soc. 272 (1982), no. 2, 383–426, DOI 10.2307/1998705. MR662044, Show rawAMSref\bib{3}{article}{ author={Hanlon, Phil}, title={Counting interval graphs}, journal={Trans. Amer. Math. Soc.}, volume={272}, date={1982}, number={2}, pages={383--426}, issn={0002-9947}, review={\MR {662044}}, doi={10.2307/1998705}, } Close amsref.
[4]
C. G. Lekkerkerker and J. Ch. Boland, Representation of a finite graph by a set of intervals on the real line, Fund. Math. 51 (1962/1963), 45–64. MR0139159, Show rawAMSref\bib{4}{article}{ author={Lekkerkerker, C. G.}, author={Boland, J. Ch.}, title={Representation of a finite graph by a set of intervals on the real line}, journal={Fund. Math.}, volume={51}, date={1962/1963}, pages={45--64}, issn={0016-2736}, review={\MR {0139159}}, } Close amsref.
[5]
N. J. A. Sloane (editor), The Online Encyclopedia of Integer Sequences, published electronically at https://oeis.org (2016).

Article Information

MSC 2010
Primary: 05C30 (Enumeration in graph theory)
Keywords
  • Interval graphs
  • enumeration
Author Information
Joyce C. Yang
Department of Mathematics, Harvey Mudd College, 301 Platt Boulevard, Claremont, California 91711
jcyang@hmc.edu
Nicholas Pippenger
Department of Mathematics, Harvey Mudd College, 301 Platt Boulevard, Claremont, California 91711
njp@math.hmc.edu
MathSciNet
Communicated by
Patricia Hersh
Journal Information
Proceedings of the American Mathematical Society, Series B, Volume 4, Issue 1, ISSN 2330-1511, published by the American Mathematical Society, Providence, Rhode Island.
Publication History
This article was received on , revised on , and published on .
Copyright Information
Copyright 2017 by the authors under Creative Commons Attribution-Noncommercial 3.0 License (CC BY NC 3.0)
Article References

Settings

Change font size
Resize article panel
Enable equation enrichment

Note. To explore an equation, focus it (e.g., by clicking on it) and use the arrow keys to navigate its structure. Screenreader users should be advised that enabling speech synthesis will lead to duplicate aural rendering.

For more information please visit the AMS MathViewer documentation.