2022/08/05 by Maryam Abdi, Ebrahim Ghorbani
Chemistry · Computer Science · Mathematics · #Graph theory and applications #Metal-Organic Frameworks: Synthesis and Applications #Topological and Geometric Data Analysis
paper · doi:10.1002/jgt.22867
openalex publication_date 2022/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26
Abstract Aldous and Fill conjectured that the maximum relaxation time for the random walk on a connected regular graph with vertices is . This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected ‐regular graph on vertices is at least , and the bound is attained for at least one value of . We determine the structure of connected quartic graphs on vertices with a minimum spectral gap which enables us to show that the minimum spectral gap of connected quartic graphs on vertices is . From this result, the Aldous–Fill conjecture follows for .