Counting Interval Graphs
- 1 August 1982
- journal article
- Published by JSTOR in Transactions of the American Mathematical Society
- Vol. 272 (2) , 383-426
- https://doi.org/10.2307/1998705
Abstract
In this paper we enumerate interval graphs (up to isomorphism) along with labelled interval graphs, identity interval graphs, transitive interval graphs and various sorts of unit interval graphs. The enumeration makes use of a structural decomposition of interval graphs which leads to a characterization of those interval graphs having a unique interval representation. Several tables are included.Keywords
This publication has 10 references indexed in Scilit:
- Monotone sequences of graphical invariantsNetworks, 1980
- Extremal Values of the Interval Number of a GraphSIAM Journal on Algebraic Discrete Methods, 1980
- Algorithmic Graph Theory and Perfect GraphsPublished by Elsevier ,1980
- Extremal values of the interval number of a graph, IIDiscrete Mathematics, 1979
- On double and multiple interval graphsJournal of Graph Theory, 1979
- The probability of an interval graph, and why it mattersPublished by American Mathematical Society (AMS) ,1979
- Asymptotic Methods in EnumerationSIAM Review, 1974
- Graphical EnumerationPublished by Elsevier ,1973
- What Are the Intersection Graphs of Arcs in a Circle?The American Mathematical Monthly, 1969
- A Characterization of Comparability Graphs and of Interval GraphsCanadian Journal of Mathematics, 1964