On the order of regular graphs with fixed second largest eigenvalue

DOI10.1016/J.LAA.2020.09.020zbMATH Open1458.05160arXiv1809.01888OpenAlexW3088439232MaRDI QIDQ2228095FDOQ2228095

Authors: Jae Young Yang, Jack H. Koolen 

Publication date: 16 February 2021

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

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$.

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

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

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)

Cites Work

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

Cited In (11)

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

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)