Generating Functions and the Entropy Hierarchy of Strongly Connected Digraphs
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 𝒮𝒞m+1(m) of strongly connected digraphs with m vertices and m+1 edges, we introduce a unified (t,k1,k2)-butterfly parametrization. The entropy of ℬ tk1,k2 depends only on (k1,k2) and is determined by the unique root R∈(0,1) of 1−zk1−zk2=0 via h=−ln R. This parametrization yields a detailed entropy hierarchy within 𝒮𝒞m+1(m). We introduce the Pyramidal Entropy Diagram, determine the entropy order completely for m≤ 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.
Related
- Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with m+2 Edges
- Sharp bounds and extremal structure of minimally strongly k-connected digraphs
- Eccentric Connectivity Index of Cartesian product and Strong product of Strongly Connected Digraphs
- Quasi-strongly regular digraphs constructed from transitive groups of degree n≤ 110
- Avoidability of Digraphs with Height Functions and Orientations of C4
BibTeX
@misc{klech2026generating,
title = {{Generating Functions and the Entropy Hierarchy of Strongly Connected Digraphs}},
author = {Rostislav Klech},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17334},
eprint = {2609.17334},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17334},
}
RIS
TY - UNPB
TI - Generating Functions and the Entropy Hierarchy of Strongly Connected Digraphs
AU - Rostislav Klech
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17334
UR - https://arxiv.org/abs/2609.17334
AB - 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 𝒮𝒞_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 ℬ^ t_k_1,k_2 depends only on (k_1,k_2) and is determined by the unique root R∈(0,1) of 1−z^k_1−z^k_2=0 via h=−ln R. This parametrization yields a detailed entropy hierarchy within 𝒮𝒞_m+1(m). We introduce the Pyramidal Entropy Diagram, determine the entropy order completely for m≤ 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.
ER -