Uniform upper bound of the second largest eigenvalue of stochastic matrices with equal-neighbor rule

Abstract

Given the number of vertices only, we provide a uniform upper bound of the second largest eigenvalue (SLE) of stochastic matrices induced from rooted graphs under the equal-neighbor rule, by acquiring a tight upper bound of its scrambling constant (SC). Furthermore, with the concept of canonical form of rooted graphs, we find the least connective topology of rooted graphs in the sense of SC. When more information on the graph topology is available, a more accurate bound is also provided. Our result is applied to estimate the convergence rate of consensus protocols studied in system and control literature Show more