In the present paper, for a given (possibly, infinite) strongly connected digraph $\cal{ D},$ we consider the class $\cal{ S}_{ <}({ \cal D})$ of all truthly substochastic weightings of ${ \cal D}$ (here, the word "truthly" means that there exists a vertex whose out-weight is strictly less than $1$). For a finite subdigraph $\cal{ F}$ of $\cal{ D}$ weighted by $S\in { \cal S}_{ <}({ \cal D}),$ let $\ell_{ max}(\cal{ F})$ be the length of its longest directed cycle and $\lambda_{ S}(\cal{ F})$ be the Perron root (spectral radius) of its weighted adjacency matrix. We prove that the infimum of $\ell_{ max}(\cal{ F})\bigl(1-\lambda_{ S}(\cal{ F})\bigr)$ taken over all $\cal{ F}$ is positive for every $S\in \cal{ S}_{ <}({ \cal D})$ if and only if $\cal{ D}$ admits a finite cycle transversal. The result obtained provides general theorems on the set ${ \cal T}({ \cal D})$ of transient weightings of ${ \cal D}.$ In particular, we present a theorem of alternatives for finite approximations to elements of ${ \cal T}({ \cal D})$ and simply reprove V. Cyr's criterion for ${ \cal T}({ \cal D})$ to be empty.

Categories: math.CO

On (Sub)stochastic and Transient Weightings of Infinite Strong Digraphs