Journal of Integer Sequences, Vol. 25 (2022), Article 22.2.7

Enumerating Threshold Graphs and Some Related Graph Classes

David Galvin, Greyson Wesley, and Bailee Zacovic
Department of Mathematics
University of Notre Dame
Notre Dame, IN 46556


We give combinatorial proofs of some enumeration formulas involving labelled threshold, quasi-threshold, loop-threshold and quasi-loop-threshold graphs. In each case we count by number of vertices and number of components. For threshold graphs, we also count by number of dominating vertices, and for loop-threshold graphs we count by number of looped dominating vertices.

We also obtain an analog of the Frobenius formula (connecting Eulerian numbers and Stirling numbers of the second kind) in the context of labelled threshold graphs.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000629 A000670 A005840 A008277 A008292 A038052 A048802 A053525 A058863 A058864 A154921 A317057 A348436 A348576 A350060 A350528 A350531 A350745 A350746.)

Received January 13 2022; revised version received March 2 2022. Published in Journal of Integer Sequences, March 2 2022.

Return to Journal of Integer Sequences home page