{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T17:20:09Z","timestamp":1765041609231,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2024,11,23]],"date-time":"2024-11-23T00:00:00Z","timestamp":1732320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSERC Discovery"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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\u22083,7, 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 d\u22658. 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 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.<\/jats:p>","DOI":"10.3390\/e26121014","type":"journal-article","created":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T03:59:01Z","timestamp":1732507141000},"page":"1014","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["It Is Better to Be Semi-Regular When You Have a Low Degree"],"prefix":"10.3390","volume":"26","author":[{"given":"Theodore","family":"Kolokolnikov","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, Dalhousie University Halifax, Halifax, NS B3H 3J5, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2024,11,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","article-title":"Algebraic connectivity of graphs","volume":"23","author":"Fiedler","year":"1973","journal-title":"Czechoslov. Math. J."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.laa.2006.08.017","article-title":"Old and new results on algebraic connectivity of graphs","volume":"423","year":"2007","journal-title":"Linear Algebra Its Appl."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Ghosh, A., and Boyd, S. (2006, January 13\u201315). Growing well-connected graphs. Proceedings of the 2006 45th IEEE Conference on Decision and Control, San Diego, CA, USA.","DOI":"10.1109\/CDC.2006.377282"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Wang, H., and Mieghem, P.V. (2008, January 25\u201328). Algebraic connectivity optimization via link addition. Proceedings of the 3rd International Conference on Bio-Inspired Models of Network, Information and Computing Sytems, Hyogo, Japan.","DOI":"10.4108\/ICST.BIONETICS2008.4691"},{"key":"ref_5","first-page":"5465","article-title":"Optimizing algebraic connectivity by edge rewiring","volume":"219","author":"Sydney","year":"2013","journal-title":"Appl. Math. Comput."},{"key":"ref_6","unstructured":"Olfati-Saber, R. (2005, January 8\u201310). Ultrafast consensus in small-world networks. Proceedings of the American Control Conference, Portland, OR, USA."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.laa.2014.12.023","article-title":"Maximizing algebraic connectivity for certain families of graphs","volume":"471","author":"Kolokolnikov","year":"2015","journal-title":"Linear Algebra Its Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1109\/TCNS.2015.2503561","article-title":"Maximizing algebraic connectivity in the space of graphs with a fixed number of vertices and edges","volume":"4","author":"Ogiwara","year":"2015","journal-title":"IEEE Trans. Control Netw. Syst."},{"key":"ref_9","unstructured":"Shahbaz, K., Belur, M.N., and Ganesh, A. (2021). Algebraic connectivity: Local and global maximizer graphs. arXiv."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1016\/j.orl.2008.09.001","article-title":"Maximum algebraic connectivity augmentation is NP-hard","volume":"36","year":"2008","journal-title":"Oper. Res. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","article-title":"Expander graphs and their applications","volume":"43","author":"Hoory","year":"2006","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/S0273-0979-2011-01359-3","article-title":"Expander graphs in pure and applied mathematics","volume":"49","author":"Lubotzky","year":"2012","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_13","first-page":"290","article-title":"On Random Graphs. I","volume":"6","author":"Erdos","year":"1959","journal-title":"Publ. Math."},{"key":"ref_14","unstructured":"Alon, N., and Spencer, J.H. (2004). The Probabilistic Method, Wiley."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0024-3795(81)90150-6","article-title":"The expected eigenvalue distribution of a large regular graph","volume":"40","author":"McKay","year":"1981","journal-title":"Linear Algebra Its Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","article-title":"Eigenvalues and expanders","volume":"6","author":"Alon","year":"1986","journal-title":"Combinatorica"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Broder, A., and Shamir, E. (1987, January 12\u201314). On the second eigenvalue of random regular graphs. Proceedings of the 28th Annual Symposium on Foundations of Computer Science, Los Angeles, CA, USA.","DOI":"10.1109\/SFCS.1987.45"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF01275669","article-title":"On the second eigenvalue and random walks in random d-regular graphs","volume":"11","author":"Friedman","year":"1991","journal-title":"Combinatorica"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"N9","DOI":"10.37236\/1850","article-title":"Tight estimates for eigenvalues of regular graphs","volume":"11","author":"Nilli","year":"2004","journal-title":"Electron. J. Comb."},{"key":"ref_20","first-page":"239","article-title":"Models of random regular graphs","volume":"267","author":"Wormald","year":"1999","journal-title":"Lond. Math. Soc. Lect. Note Ser."},{"key":"ref_21","first-page":"33","article-title":"Ramanujan graphs","volume":"18","author":"Murty","year":"2003","journal-title":"J.-Ramanujan Math. Soc."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"548","DOI":"10.2307\/1970079","article-title":"Characteristic vectors of bordered matrices with infinite dimensions","volume":"62","author":"Wigner","year":"1955","journal-title":"Ann. Math."},{"key":"ref_23","unstructured":"Longoria, I.S.A., and Mingo, J.A. (2020). Freely independent coin tosses, standard Young tableaux, and the Kesten\u2013McKay law. arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Mingo, J.A., and Speicher, R. (2017). Free Probability and Random Matrices, Springer.","DOI":"10.1007\/978-1-4939-6942-5"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Wilf, H.S. (2005). Generatingfunctionology, CRC Press.","DOI":"10.1201\/b10576"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.dam.2014.05.048","article-title":"The average reliability of a graph","volume":"177","author":"Brown","year":"2014","journal-title":"Discret. Appl. Math."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s11786-018-0345-5","article-title":"Sixty years of network reliability","volume":"12","year":"2018","journal-title":"Math. Comput. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Exoo, G., and Jajcay, R. (2012). Dynamic cage survey. Electron. J. Comb., DS16.","DOI":"10.37236\/37"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"A1","DOI":"10.37236\/1386","article-title":"Constructions for cubic graphs with large girth","volume":"5","author":"Biggs","year":"1998","journal-title":"Electron. J. Comb."},{"key":"ref_30","unstructured":"McKay, B., Myrvold, W., and Nadon, J. (1998, January 25\u201327). Fast backtracking principles applied to find new cages. Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.jda.2010.11.001","article-title":"Computational determination of (3, 11) and (4, 7) cages","volume":"9","author":"Exoo","year":"2011","journal-title":"J. Discret. Algorithms"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0095-8956(79)90052-2","article-title":"A smallest graph of girth 5 and valency 6","volume":"26","author":"Wong","year":"1979","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.4153\/CJM-1966-109-8","article-title":"Minimal regular graphs of girths eight and twelve","volume":"18","author":"Benson","year":"1966","journal-title":"Can. J. Math."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/12\/1014\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:38:10Z","timestamp":1760114290000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/26\/12\/1014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,23]]},"references-count":33,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["e26121014"],"URL":"https:\/\/doi.org\/10.3390\/e26121014","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2024,11,23]]}}}