  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 and as well as the full
spectrum distribution. For an integer $d\in\left[ 3,7\right] $, we find
families of random semi-regular graphs that have higher algebraic connectivity
than a 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
$d\geq8.$ More generally, we study random semi-regular graphs whose average
degree is $d$, not necessary an integer. This provides a natural generalization
of a $d$-regular graph in the case of a non-integer $d.$ We characterise their
algebraic connectivity in terms of a root of a certain 6th-degree polynomial.
Finally, we construct a small-world-type network of average degree 2.5 with a
relatively high algebraic connectivity. We also propose some related open
problems and conjectures.
