Enumeration of labelled threshold graphs and a theorem of frobenius involving eulerian polynomials

Springer Science and Business Media LLC - Tập 3 - Trang 213-219 - 1987
Janet Simpson Beissinger1, Uri N. Peled1
1Department of Mathematics, Statistics, and Computer Science, University of Ilinois at Chicago, Chicago, USA

Tóm tắt

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.

Tài liệu tham khảo

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