Load balancing for Markov chains with a specified directed graph

Given a strongly directed graph D, let Sigma(D) be the set of stochastic matrices whose directed graph is a spanning subgraph of D. We consider the problem of finding the infimum of || x||(infinity) as x ranges over the set of stationary distribution vectors of irreducible matrices in Sigma(D). Using techniques from non-linear programming, combinatorial matrix theory and non-negativematrix theory, wefind this infimum, which is given in terms the cardinality of a certain collection of vertex-disjoint cycles in D. The situation that the infimum is attained as a minimum for the stationary distribution vector of some irreducible matrix in Sigma(D) is also considered.