On the extreme eigenvalues of regular graphs.

DOI10.1016/J.JCTB.2005.09.002MaRDI QIDQ2490837zbMATH OpenOpenAlexFDO

Authors Sebastian Cioaba

Publication date 18 May 2006

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

Alon-Boppana theoremeigenvalues of graphsgraph spectrumregular graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Algebraic combinatorics (05E99)

Abstract: In this paper, we present an elementary proof of a theorem of Serre concerning the greatest eigenvalues of $k$-regular graphs. We also prove an analogue of Serre's theorem regarding the least eigenvalues of $k$-regular graphs: given $epsilon>0$, there exist a positive constant $c=c(epsilon,k)$ and a nonnegative integer $g=g(epsilon,k)$ such that for any $k$-regular graph $X$ with no odd cycles of length less than $g$, the number of eigenvalues $mu$ of $X$ such that $muleq-(2-epsilon)sqrtk-1$ is at least $c|X|$. This implies a result of Winnie Li.

Review text

The author gives elementary proofs of results of Serre and Li on extreme eigenvalues of regular graphs.

Cites work

• Eigenvalues and expanders
• scientific article; zbMATH DE number 1210372 (Why is no real title available?)
• scientific article; zbMATH DE number 1849959 (Why is no real title available?)
• scientific article; zbMATH DE number 823142 (Why is no real title available?)
• On negative eigenvalues of regular graphs
• On the second eigenvalue of a graph
• Ramanujan graphs
• Répartition asymptotique des valeurs propres de l’opérateur de Hecke 𝑇_𝑝
• Some geometric aspects of graphs and their eigenfunctions
• Spectra of hypergraphs and applications
• Spectra of regular graphs and hypergraphs and orthogonal polynomials
• The expected eigenvalue distribution of a large regular graph
• Tight estimates for eigenvalues of regular graphs

Cited in

(18)

• Extremal properties of eigenvalues for a metric graph.
• Tight estimates for eigenvalues of regular graphs
• The maximum spectral radius of non-bipartite graphs forbidding short odd cycles
• Eigenvalues of Cayley graphs
• On the order of regular graphs with fixed second largest eigenvalue
• Some observations on the smallest adjacency eigenvalue of a graph
• Median eigenvalues and the HOMO-LUMO index of graphs
• Eigenvalues of graphs and a simple proof of a theorem of Greenberg
• Closed walks and eigenvalues of abelian Cayley graphs
• Maximizing the order of a regular graph of given valency and second eigenvalue
• Fixation and escape times in stochastic game learning
• Expander graphs and their applications
• Explicit bounds from the Alon-Boppana theorem
• A spectral Erdős-Rademacher theorem
• Cubic graphs with no eigenvalues in the interval (-1,1)
• Limit vectors of the top k eigenvalues of d-regular graphs
• Eigenvalues and forbidden subgraphs. I.
• Extreme eigenvalues of nonregular graphs

This page was built for publication: On the extreme eigenvalues of regular graphs.

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