Kolokolnikov Theodore
Department of Mathematics and Statistics, Dalhousie University Halifax, Halifax, NS B3H 3J5, Canada.
Entropy (Basel). 2024 Nov 23;26(12):1014. doi: 10.3390/e26121014.
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 -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 , not necessarily an integer. This provides a natural generalization of a -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.
我们研究了几类随机半正则图的代数连通性。对于大型随机半正则二分图，我们明确计算了它们的代数连通性以及完整的谱分布。对于整数(d\in{3,7})，我们找到了一些随机半正则图族，它们的代数连通性高于具有相同顶点数和边数的随机正则图。另一方面，我们表明当(d\geq8)时，正则图优于半正则图。更一般地，我们研究平均度为(\mu)（不一定是整数）的随机半正则图。这在非整数(d)的情况下提供了正则图的自然推广。我们根据某个六次多项式的根来刻画它们的代数连通性。最后，我们构建了一个平均度为(2.5)且代数连通性相对较高的小世界型网络。我们还提出了一些相关的开放问题和猜想。
