Counting labeled threshold graphs with Eulerian numbers
Counting labeled threshold graphs with Eulerian numbers
复制标题
用欧拉数计算标记阈值图
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Sam Spiro
中科院分区：
文献类型：
--
作者：
Sam Spiro
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}{
angle}{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 $nge 2$ vertices is
[sum_{k=1}^{n-1}(n-k)genfrac{langle}{
angle}{0pt}{}{n-1}{k-1}2^k.]
Their proof used generating functions. We give a direct combinatorial proof of this result.
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}{
angle}{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 $nge 2$ vertices is
[sum_{k=1}^{n-1}(n-k)genfrac{langle}{
angle}{0pt}{}{n-1}{k-1}2^k.]
Their proof used generating functions. We give a direct combinatorial proof of this result.