Counting Labeled Threshold Graphs with Eulerian Numbers

MaRDI QIDQ3300701zbMATH OpenFDO

Authors Sam Spiro

Publication date 29 July 2020

Full work available at URL https://arxiv.org/abs/1909.06518, http://ajc.maths.uq.edu.au/pdf/77/ajc_v77_p249.pdf

zbMATH Keywords

exponential generating functionthreshold pair

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Bernoulli and Euler numbers and polynomials (11B68)

Abstract: 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 $genfraclangleangle0ptnk$ 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 $nge2$ 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.

Recommendations

• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Enumerating threshold graphs and some related graph classes
• A combinatorial statistic for labeled threshold graphs
• scientific article; zbMATH DE number 1558262
• scientific article; zbMATH DE number 6466113
• Enumeration of labeled bicyclic and tricyclic Eulerian graphs
• The enumeration of labeled graphs by number of cutpoints
• Interval count of generalizations of threshold graphs
• Enumeration of labeled Eulerian pentacyclic graphs
• scientific article; zbMATH DE number 4033780

Cites work

• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• Ballot permutations and odd order permutations
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Oriented threshold graphs
• Threshold graph limits and random threshold graphs
• Threshold graphs and related topics

Cited in

(6)

• A combinatorial statistic for labeled threshold graphs
• Oriented threshold graphs
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Enumerating threshold graphs and some related graph classes
• Counting regions of the boxed threshold arrangement
• Permutations représentatives d'un graphe à seuil

This page was built for publication: Counting Labeled Threshold Graphs with Eulerian Numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300701)