Algebraic Connectivity Maximizing Regular Graphs: Special Case Analysis and Depth‐First Search

The algebraic connectivity is an indicator of how well connected a graph is. It also characterizes the convergence speed of some dynamic processes over networks. In this paper, taking into account that homogeneous networks are modeled as regular graphs, we tackle the following problem: given a pair (𝑛, 𝑘) of positive integers such that 𝑘 is less than 𝑛 and kn is an even number, find a 𝑘-regular graph with 𝑛 vertices that have the maximum algebraic connectivity. We first consider some special cases and derive solutions through theoretical analysis. We next present depth-first search algorithms for solving the problem, which reduce the search space by making use of some known properties of the regular graph and the algebraic connectivity.We also show the results of execution of the proposed algorithms for the values of 𝑛 up to 12.