Enumerating Threshold Graphs and Some Related Graph Classes
Published in Journal of Integer Sequences, 2022
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.
(Concerned with sequences A000629 A000670 A005840 A008277 A008292 A038052 A048802 A053525 A058863 A058864 A154921 A317057 A348436 A348576 A350060 A350528 A350531 A350745 A350746.)
Recommended citation: David Galvin, Greyson Wesley, and Bailee Zacovic. "Enumerating Threshold Graphs and Some Related Graph Classes". Journal of Integer Sequences. 25 (2022), Article 22.2.7.
Download Paper