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,
(Concerned with sequences
Received January 13 2022; revised version received March 2 2022.
Published in Journal of Integer Sequences,
March 2 2022.
Journal of Integer Sequences home page