Counting Labeled Threshold Graphs with Eulerian Numbers

A threshold graph is any graph which can be constructed from the empty graph by repeatedly adding a new vertex that is either adjacent to every vertex or to no vertices. The Eulerian number $\genfrac{\langle}{\rangle}{0pt}{}{n}{k}$ counts the number of permutations of size $n$ with exactly $k$ ascents. Implicitly Beissinger and Peled proved that the number of labeled threshold graphs on $n\ge 2$ vertices is $\sum_{k=1}^{n-1}(n-k)\genfrac{\langle}{\rangle}{0pt}{}{n-1}{k-1}2^k.$ Their proof used generating functions. We give a direct combinatorial proof of this result.

No reviews yet.

No comments yet.