Counting Labeled Threshold Graphs with Eulerian Numbers

zbMATH Open1444.05069arXiv1909.06518MaRDI QIDQ3300701FDOQ3300701

Authors: Sam Spiro 

Publication date: 29 July 2020

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.

Full work available at URL: https://arxiv.org/abs/1909.06518

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

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)

Cites Work

• Threshold graphs and related topics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Threshold graph limits and random threshold graphs
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• Oriented threshold graphs
• Ballot permutations and odd order permutations

Cited In (6)

• Oriented threshold graphs
• A combinatorial statistic for labeled threshold graphs
• Enumerating threshold graphs and some related graph classes
• Counting regions of the boxed threshold arrangement
• Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
• 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)