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

Theodore Kolokolnikov, Lu Wei · 2024

Read It Is Better to Be Semi-Regular When You Have a Low Degree by Theodore Kolokolnikov, Lu Wei (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/pmc-11727215.txt.

Description

How well connected a network is can be read from a number called algebraic connectivity, and random regular graphs are the usual benchmark. Theodore Kolokolnikov and Lu Wei ask in 2024 whether semi-regular graphs, where two camps of nodes carry unlike degrees, can do better. For large random semi-regular bipartite graphs, they compute the connectivity and the full spectrum exactly.

For low degrees, from three to seven, their families of semi-regular graphs beat regular graphs with the same size. From degree eight up, regular graphs win again. They also handle non-integer average degree with a sixth-degree polynomial rule, and they build a small-world style network of average degree two and a half with strikingly high connectivity. Open problems close the paper.

Catalog record

CREATORTheodore Kolokolnikov, Lu Wei
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSECC BY 4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/articles/PMC11727215

Browse the full library · About the Tower of Babel