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

Abstract

We study the minimum adjacency spectral radius in the class $\mathcal{SC}_{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 $\mathcal{SC}_{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\in(0,1)$ denotes its unique root, then $\min_{G\in\mathcal{SC}_{m+2}(m)}\rho(G)=R_m^{-1}$. For $m\geq4$, the minimum is attained, up to isomorphism, uniquely by the cross-chorded cycle $\mathcal{C}_m^\times$. For $m=3$, there are exactly two non-isomorphic minimizers, both with spectral radius $(1+\sqrt5)/2$. Finally, we establish the bounds $2^{1/(m-1)}<\rho\left(\mathcal{C}_m^\times\right)<3^{1/(m-1)}$.