The algebraic connectivity of unicyclic digraphs

The algebraic connectivity of a digraph is the second smallest real part among the Laplacian eigenvalues of the digraph. The digraphs which contain exactly one vertex of in-degree zero are usually used in leader–follower multi-agent systems (MASs) as their interaction topologies. Note that the unicyclic digraphs are useful in the cluster consensus problem in MASs, and in the hybrid evolution in molecular evolutionary biology, and so on. Therefore, we focus on the unicyclic digraphs which have exactly one vertex of in-degree zero in this paper. We determine the digraphs maximizing and minimizing the algebraic connectivity among all unicyclic digraphs with given order and in-degree sequence, respectively. For the MASs with unicyclic digraphs as their interaction topologies, the extremal digraphs characterize the interaction topologies with the fastest and slowest consensus convergence rate. Moreover, we investigate the effects on the algebraic connectivity under adding one arc to some classes of unicyclic digraphs, and determine which arcs will lead to the maximum increase on the algebraic connectivity. These results extend previous findings on how the algebraic connectivity changes under adding some reverse arcs to an acyclic digraph.