It Is Better to Be Semi-Regular When You Have a Low Degree - Theodore Kolokolnikov (Entropy)
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 <semantics>d∈<mfenced separators="" open="[" close="]">3,7</mfenced></semantics>, we find families of random semi-regular graphs that have higher algebraic connectivity than random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when <semantics>d≥8</semantics>. More generally, we study random semi-regular graphs whose average degree is d, not necessarily an integer. This provides a natural generalization of a d-regular graph in the case of a non-integer <semantics>d</semantics>. 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.