On the enumeration of interval graphs
HTML articles powered by AMS MathViewer
- by Joyce C. Yang and Nicholas Pippenger HTML | PDF
- Proc. Amer. Math. Soc. Ser. B 4 (2017), 1-3
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$.References
- 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).
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
- 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
- © Copyright 2017 by the authors under Creative Commons Attribution-Noncommercial 3.0 License (CC BY NC 3.0)
- Journal: Proc. Amer. Math. Soc. Ser. B 4 (2017), 1-3
- MSC (2010): Primary 05C30
- DOI: https://doi.org/10.1090/bproc/27
- MathSciNet review: 3613306