Regular graphs with minimum spectral gap

DOI10.1016/J.EJC.2021.103328MaRDI QIDQ2033936zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 18 June 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.03733

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81)

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))frac3n^{2}2p{i}^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))frac2kp{i}^{2}3n^2$, 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.

Recommendations

• Quartic graphs with minimum spectral gap
• The structure of trivalent graphs with minimal eigenvalue gap
• Gap sets for the spectra of regular graphs with minimum spectral gap
• The maximum relaxation time of a random walk
• Graphs with small spectral gap

Cites work

• scientific article; zbMATH DE number 3503313 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Cubic graphs on \(\leq 14\) vertices
• The maximum relaxation time of a random walk
• The structure of trivalent graphs with minimal eigenvalue gap

Cited in

(9)

• Graphs with small spectral gap
• Extremal spectral radius of nonregular graphs with prescribed maximum degree
• Maximum spread of graphs and bipartite graphs
• Graphs of degree at least \({3}\) with minimum algebraic connectivity
• The maximum relaxation time of a random walk
• Quartic graphs with minimum spectral gap
• Minimum algebraic connectivity and maximum diameter: Aldous-Fill and Guiduli-Mohar conjectures
• The maximum spectral radius of irregular bipartite graphs
• Gap sets for the spectra of regular graphs with minimum spectral gap

This page was built for publication: Regular graphs with minimum spectral gap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2033936)