Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with m+2 Edges

@misc{klech2026generating,
  title = {{Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with $m+2$ Edges}},
  author = {Rostislav Klech},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.18367},
  eprint = {2609.18367},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.18367},
}

TY  - UNPB
TI  - Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with m+2 Edges
AU  - Rostislav Klech
PY  - 2026
DA  - 2026/09/16
PB  - arXiv
DO  - 10.48550/arxiv.2609.18367
UR  - https://arxiv.org/abs/2609.18367
AB  - We study the minimum adjacency spectral radius in the class 𝒮𝒞_m+2(m) of strongly connected digraphs with m vertices and m+2 edges. Using generating functions for directed paths, we associate with the relevant digraphs topological polynomials whose smallest positive roots determine the corresponding spectral radii. Based on an ear decomposition, we obtain a complete structural classification of 𝒮𝒞_m+2(m) by showing that every digraph in this class can be obtained from a butterfly digraph by attaching a single ear. This reduces the extremal problem to the optimization and comparison of finitely many polynomial families subject to their realizability conditions. We prove that the minimum spectral radius is determined by the polynomial P_min(z)=1−2z^m−1−z^m. If R_m∈(0,1) denotes its unique root, then min_G∈𝒮𝒞_m+2(m)ρ(G)=R_m^−1. For m≥4, the minimum is attained, up to isomorphism, uniquely by the cross-chorded cycle 𝒞_m^×. For m=3, there are exactly two non-isomorphic minimizers, both with spectral radius (1+√5)/2. Finally, we establish the bounds 2^1/(m−1)<ρ(𝒞_m^×)<3^1/(m−1).
ER  -