The effect of adding one edge between two chain networks on the consensus convergence rate

Where to add edges between interacting networks of multiple multi-agent systems (MAS) to make the resulting MAS achieve consensus and have the fastest consensus convergence rate is an meaningful work in the study of the consensus problem of MASs. However, there are few works considering this theme. For a first-order MAS with the interaction network represented as an undirected graph, improving the system's consensus convergence rate is equivalent to increasing the algebraic connectivity of the undirected graph. This paper investigates the effect of adding one edge between two chain networks on the consensus convergence rate. Firstly, all optimal approaches of adding one edge that maximize the algebraic connectivity are given. Then, considering the case where one of the end-vertices of the edge added is fixed, not only all optimal approaches to adding an edge that maximize algebraic connectivity are given, but also an ordering of all possible approaches to adding an edge based on algebraic connectivity. The ordering can be used as a criterion on how to choose an optimal one among the feasible approaches to adding one edge when the optimal approaches are not achievable. Finally, numerical examples are provided to verify the theoretical results, and potential directions for further research are discussed.