It Is Better to Be Semi-Regular When You Have a Low Degree

We study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity as well as the full spectrum distribution. For an integer d∈3,7, we find families of random semi-regular graphs that have higher algebraic connectivity than random <i>d</i>-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when d≥8. More generally, we study random semi-regular graphs whose average degree is <i>d</i>, not necessarily an integer. This provides a natural generalization of a <i>d</i>-regular graph in the case of a non-integer d. We characterize their algebraic connectivity in terms of a root of a certain sixth-degree polynomial. Finally, we construct a small-world-type network of an average degree of 2.5 with relatively high algebraic connectivity. We also propose some related open problems and conjectures.