On the enumeration of interval graphs
Authors:
Joyce C. Yang and Nicholas Pippenger
Journal:
Proc. Amer. Math. Soc. Ser. B 4 (2017), 1-3
MSC (2010):
Primary 05C30
DOI:
https://doi.org/10.1090/bproc/27
Published electronically:
February 24, 2017
MathSciNet review:
3613306
Full-text PDF Open Access
View in AMS MathViewer
Abstract | References | Similar Articles | Additional Information
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$.
- S. Benzer, On the topology of the genetic fine structure, Proc. Nat. Acad. Sci. 45 (1959), 1607–1620.
- G. Hajós, Über eine Art von Graphen, Int. Math. Nachr. 11 (1957), 65 pp.
- Phil Hanlon, Counting interval graphs, Trans. Amer. Math. Soc. 272 (1982), no. 2, 383–426. MR 662044, DOI 10.1090/S0002-9947-1982-0662044-8
- 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/63), 45–64. MR 139159, DOI 10.4064/fm-51-1-45-64
- N. J. A. Sloane (editor), The Online Encyclopedia of Integer Sequences, published electronically at https://oeis.org (2016).
Retrieve articles in Proceedings of the American Mathematical Society, Series B with MSC (2010): 05C30
Retrieve articles in all journals with MSC (2010): 05C30
Additional Information
Joyce C. Yang
Affiliation:
Department of Mathematics, Harvey Mudd College, 301 Platt Boulevard, Claremont, California 91711
Email:
jcyang@hmc.edu
Nicholas Pippenger
Affiliation:
Department of Mathematics, Harvey Mudd College, 301 Platt Boulevard, Claremont, California 91711
MR Author ID:
139890
Email:
njp@math.hmc.edu
Keywords:
Interval graphs,
enumeration
Received by editor(s):
September 24, 2016
Received by editor(s) in revised form:
October 24, 2016
Published electronically:
February 24, 2017
Communicated by:
Patricia Hersh
Article copyright:
© Copyright 2017
by the authors under
Creative Commons Attribution-Noncommercial 3.0 License
(CC BY NC 3.0)