Counting acyclic and strong digraphs by descents (Q2198383)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Counting acyclic and strong digraphs by descents |
scientific article |
Statements
Counting acyclic and strong digraphs by descents (English)
0 references
10 September 2020
0 references
In this paper, the authors refine the counting formulas for four classes of labeled directed graphs with \(n\) nodes and \(m\) edges by additional accounting for the number of descents. Hereby, a descent is a directed edge \((s,t)\) with \(s > t\). The considered classes are strongly connected tournaments, strongly connected directed graphs, acyclic directed graphs, and forests (or trees). Their method builds on the known recursive formulas for these classes which are enriched by the number of descents. Then, they use special types of generating functions, such as Eulerian generating functions and a new variant developed by them called graphic Eulerian generating function, to derive closed forms or functional equations.
0 references
acyclic digraph
0 references
strongly connected digraph
0 references
strongly connected tournament
0 references
descent
0 references
Eulerian generating function
0 references
graphic generating function
0 references