Abstract
We enumerate labelled threshold graphs by the number of vertices, the number of isolated vertices, and the number of distinct vertex-degrees and we give the exact asymptotics for the number of labelled threshold graphs withn vertices. We obtain the appropriate generating function and point out a combinatorial interpretation relating its coefficients to the Stirling numbers of the second kind. We use these results to derive a new proof of a theorem of Frobenius expressing the Eulerian polynomials in terms of the Stirling numbers.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bender, E.A.: Asymptotic methods in enumeration. SIAM Rev.16, 485–515 (1974)
Chvátal, V., Hammer, P.L.: Aggregation of inequalities in integer programming. Ann. Discrete Math.1, 145–162 (1977)
Comtet, L.: Advanced Combinatorics. Dordrecht-Holland: Reidel 1974
Frobenius, G.: Über die Bernoullischen und die Eulerschen Polynome. Sitzungsberichte der Preussische Akademie der Wissenschaften 809–847 (1910)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press 1980
Knuth, D.E.: The Art of Computer Programming, vol. 3. Reading: Addison-Wesley 1973
Peled, U.N.: Threshold graph enumeration and series-product identities. In: Proc. Eleventh Southeastern Conf. on Combinatorics, Graph Theory and Computing, pp. 735–738. Winnipeg: Utilitas Mathematica 1980
Riordan, J.: An Introduction to Combinatorial Analysis. New York: John Wiley and Sons 1958
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Beissinger, J.S., Peled, U.N. Enumeration of labelled threshold graphs and a theorem of frobenius involving eulerian polynomials. Graphs and Combinatorics 3, 213–219 (1987). https://doi.org/10.1007/BF01788543
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01788543