Two sufficient conditions for altering algebraic connectivity via edge addition in single-root digraphs

This paper studies how adding an edge affects the second smallest eigenvalue λ2 of the Laplacian matrix in single-root digraphs, aiming to determine whether such an addition increases, decreases, or leaves λ2 unchanged. First, a spectral framework built via the block lower-triangular decomposition induced by strongly connected components (SCCs) to distinguish each SCC's contribution to the overall spectrum enables the establishment of two sufficient conditions using matrix perturbation theory, adjugate-matrix identities, and properties of irreducible M-matrices. Specifically, when the algebraic multiplicity of λ2 is one, these two conditions serve as criteria for the change in λ2: The first corresponds to cases of increase or no change and the second to cases of a strict decrease. Second, it is shown that when the algebraic multiplicity of λ2 exceeds one, λ2 can remain invariant under specific structural constraints on the added edge. Finally, numerical simulations on Erdős-Rényi and scale-free networks validate the theoretical criteria and reveal topology-dependent variations in the magnitude of change in λ2. Furthermore, applications to Kuramoto oscillator networks demonstrate that edge additions predicted to decrease λ2 lead to slower synchronization, confirming the dynamical significance of the proposed spectral conditions.