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

Area of Science:

• Graph theory
• Network science
• Spectral graph theory

Background:

• Algebraic connectivity is a key metric for graph robustness and information flow.
• Random semi-regular graphs offer a flexible framework for network modeling.

Purpose of the Study:

• To compute and analyze the algebraic connectivity of various random semi-regular graphs.
• To compare the algebraic connectivity of semi-regular graphs against traditional regular graphs.
• To generalize findings for non-integer average degrees and construct specific network types.

Main Methods:

• Explicit computation of algebraic connectivity and spectrum distribution for large random semi-regular bipartite graphs.
• Comparative analysis of algebraic connectivity for different graph classes based on average degree (d).
• Characterization of algebraic connectivity using polynomial roots for generalized random semi-regular graphs.

Main Results:

• Families of random semi-regular graphs exhibit higher algebraic connectivity than d-regular graphs for d in {3, 7}.
• d-regular graphs demonstrate superior algebraic connectivity for d ≥ 8.
• Algebraic connectivity for generalized random semi-regular graphs is linked to a sixth-degree polynomial root.
• A small-world network with an average degree of 2.5 was constructed with high algebraic connectivity.

Conclusions:

• The relationship between algebraic connectivity and graph regularity depends on the average degree.
• Random semi-regular graphs provide tunable properties for network design.
• Further research is needed on open problems and conjectures in spectral graph theory for random networks.