Generating Functions and the Entropy Hierarchy of Strongly Connected Digraphs

Source abstract

We present a generating-function approach to the topological entropy of finite strongly connected digraphs, working throughout with digraphs in which loops are allowed but multiple edges are excluded. Using dominant singularities of path-generating functions, we recover by new analytic--combinatorial arguments the known first and second positive-entropy minimizers from the previously studied loopless spectral setting, and extend the corresponding extremal statements to the present framework. For the class $\mathcal{SC}_{m+1}(m)$ of strongly connected digraphs with $m$ vertices and $m+1$ edges, we introduce a unified $(t,k_1,k_2)$-butterfly parametrization. The entropy of $\mathcal{B}^{\,t}_{k_1,k_2}$ depends only on $(k_1,k_2)$ and is determined by the unique root $R\in(0,1)$ of $1-z^{k_1}-z^{k_2}=0$ via $h=-\ln R$. This parametrization yields a detailed entropy hierarchy within $\mathcal{SC}_{m+1}(m)$. We introduce the Pyramidal Entropy Diagram, determine the entropy order completely for $m\leq 7$, and identify its first structural bifurcation at $m=8$. We further establish maximal stable initial and terminal segments consisting of ten entropy minima and two entropy maxima, respectively, and derive an explicit formula for the minimum order required to realize a positive entropy not exceeding a prescribed threshold.