On the order of regular graphs with fixed second largest eigenvalue

DOI10.1016/J.LAA.2020.09.020MaRDI QIDQ2228095zbMATH OpenOpenAlexFDO

Authors Jae Young Yang, Jack H. Koolen

Publication date 16 February 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

smallest eigenvalueHoffman graphAlon-Boppana theoremco-edge-regular graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Abstract: Let $v(k,lambda)$ be the maximum number of vertices of a connected $k$-regular graph with second largest eigenvalue at most $lambda$. The Alon-Boppana Theorem implies that $v(k,lambda)$ is finite when $k>fraclambd{a}^2+44$. In this paper, we show that for fixed $lambdageq1$, there exists a constant $C(lambda)$ such that $2k+2leqv(k,lambda)leq2k+C(lambda)$ when $k>fraclambd{a}^2+44$.

Recommendations

• Maximizing the order of a regular graph of given valency and second eigenvalue
• Regular graphs whose second largest eigenvalue is at most 1
• Regular graphs with small second largest eigenvalue
• Explicit bounds from the Alon-Boppana theorem
• On the second eigenvalue of a graph

Cites work

• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3528270 (Why is no real title available?)
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
• A structure theory for graphs with fixed smallest eigenvalue
• Eigenvalues and expanders
• Expander graphs and their applications
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Maximizing the order of a regular graph of given valency and second eigenvalue
• On fat Hoffman graphs with smallest eigenvalue at least -3
• On graphs whose least eigenvalue exceeds \(-1-\sqrt2\)
• On graphs whose smallest eigenvalue is at least \(-1-\sqrt 2\)
• On the extreme eigenvalues of regular graphs.
• On the second eigenvalue of a graph
• Some geometric aspects of graphs and their eigenfunctions
• Strongly regular graphs with smallest eigenvalue -m
• Tight estimates for eigenvalues of regular graphs

Cited in

(11)

• Maximizing the order of a regular graph of given valency and second eigenvalue
• Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey
• Sesqui-regular graphs with fixed smallest eigenvalue
• A spectral characterization of the \(s\)-clique extension of the triangular graphs
• The second largest eigenvalue and vertex-connectivity of regular multigraphs
• Explicit bounds from the Alon-Boppana theorem
• Regular graphs with girth at least 5 and small second largest eigenvalue
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
• On second order degree of graphs
• scientific article; zbMATH DE number 475377 (Why is no real title available?)
• Regular graphs whose second largest eigenvalue is at most 1

This page was built for publication: On the order of regular graphs with fixed second largest eigenvalue

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