Regular Graphs with Minimum Spectral Gap

2019/07/08 by Maryam Abdi, Abdi, M., Ebrahim Ghorbani +3 · 1 citation
Materials Science · Mathematics · #05C50 #60G50 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Nanocluster Synthesis and Applications #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1907.03733

openalex publication_date 2019/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Aldous and Fill conjectured that the maximum relaxation time for the random walk on a connected regular graph with n vertices is (1+o(1)) (3n²)/(2π²). This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected k-regular graph on n vertices is at least (1+o(1))(2kπ²)/(3n²), and the bound is attained for at least one value of k. Based upon previous work of Brand, Guiduli, and Imrich, we prove this conjecture for cubic graphs. We also investigate the structure of quartic (i.e. 4-regular) graphs with the minimum spectral gap among all connected quartic graphs. We show that they must have a path-like structure built from specific blocks.

Citations

• The Structure of Trivalent Graphs with Minimal Eigenvalue Gap

Cited by

• Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metrics

Related

• Quartic Graphs with Minimum Spectral Gap
• Quartic graphs with minimum spectral gap
• Minimum algebraic connectivity and maximum diameter: Aldous--Fill and Guiduli--Mohar conjectures
• Attainable bounds for algebraic connectivity and maximally-connected regular graphs
• A Nordhaus--Gaddum problem for the spectral gap of a graph