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

Area of Science:

• Graph theory
• Spectral graph theory
• Network science

Background:

• The Laplacian matrix and its eigenvalues are crucial for understanding graph properties.
• The second smallest eigenvalue (λ2) is linked to graph connectivity and dynamics.
• Analyzing eigenvalue changes upon edge modification is vital for network analysis.

Purpose of the Study:

• To investigate the effect of adding an edge on the second smallest eigenvalue (λ2) of the Laplacian matrix in single-root digraphs.
• To develop criteria for predicting whether λ2 increases, decreases, or remains unchanged.
• To explore the dynamical implications of these spectral changes in real-world networks.

Main Methods:

• Developed a spectral framework using block lower-triangular decomposition of strongly connected components (SCCs).
• Applied matrix perturbation theory, adjugate-matrix identities, and M-matrix properties to derive conditions.
• Validated theoretical criteria through numerical simulations on Erdős-Rényi and scale-free networks.

Main Results:

• Established two sufficient conditions for predicting changes in λ2 when its algebraic multiplicity is one.
• Demonstrated that λ2 can remain invariant under specific structural constraints when its algebraic multiplicity exceeds one.
• Numerical simulations confirmed theoretical predictions and revealed topology-dependent variations in λ2 change magnitude.

Conclusions:

• The study provides precise criteria for predicting spectral changes in digraphs upon edge addition.
• Edge additions predicted to decrease λ2 correlate with slower synchronization in Kuramoto oscillator networks.
• The findings highlight the dynamical significance of spectral properties in network behavior.