GRAPH-THEORETIC ASPECTS OF MAXIMIZING THE SPECTRAL-RADIUS OF NONNEGATIVE MATRICES

Let rho(i)(t) = rho(A + tE(ii)) denote the spectral radius of the sum of an irreducible nonnegative matrix A and a matrix tE(ii) that has a single nonzero entry, namely t > 0 in the i, i position. We consider q ualitative aspects of maximizing rho(i)(t), especially identifying max imizing indices i, and indices i and j that tie [i.e., rho(i)(t) = rho (j)(t) for all t > 0]. If the digraph of A is a directed cycle, then a ll vertices tie; whereas if the digraph of A is a star, then the cente r is the unique maximizing vertex. When A is the (0, 1) adjacency matr ix of a graph, we give sufficient conditions in terms of the orbits of vertices for a tie. For complete bipartite graphs and for paths, vert ices i are identified that maximize rho(i)(t) for all t > 0. However, even for a tree, it is not in general true that some fixed vertex i ma ximizes rho(i)(t) for all t > 0. (C) Elsevier Science Inc., 1997.