Remote Access Proceedings of the American Mathematical Society Series B
Gold Open Access

Proceedings of the American Mathematical Society Series B

ISSN 2330-1511

   
 
 

 

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
Full-text PDF
View in AMS MathViewer New

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$.


References [Enhancements On Off] (What's this?)


Similar Articles

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
Email: njp@math.hmc.edu

DOI: https://doi.org/10.1090/bproc/27
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 author under Creative Commons Attribution-Noncommercial 3.0 License (CC BY NC 3.0)

American Mathematical Society