Maximizing the order of a regular graph of given valency and second eigenvalue

DOI10.1137/15M1030935MaRDI QIDQ2818201zbMATH OpenOpenAlexFDO

Authors Sebastian Cioaba, Hiroshi Nozaki, Jason R. Vermette, Jack H. Koolen

Publication date 6 September 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

regular graphexpandersecond eigenvalue

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Linear programming (90C05) Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35)

Abstract: From Alon and Boppana, and Serre, we know that for any given integer $kgeq3$ and real number $lambda<2sqrtk-1$, there are finitely many $k$-regular graphs whose second largest eigenvalue is at most $lambda$. In this paper, we investigate the largest number of vertices of such graphs.

Recommendations

• On the order of regular graphs with fixed second largest eigenvalue
• The maximum valency of regular graphs with given order and odd girth
• Regular graphs whose second largest eigenvalue is at most 1
• The second largest eigenvalue and vertex-connectivity of regular multigraphs
• On graphs whose second largest eigenvalue is at most 1
• The maximum order of adjacency matrices of graphs with a given rank
• The second largest eigenvalues of regular bipartite graphs
• scientific article; zbMATH DE number 1932947
• A relationship between the second largest eigenvalue and local valency of an edge-regular graph
• On the largest eigenvalue of non-regular graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3528270 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3046496 (Why is no real title available?)
• A Minimal Cubic Graph of Girth Seven
• A continuous analogue of the girth problem
• A graph which is edge transitive but not arc transitive
• A simple group of order 44,352,000
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
• Characterization of the odd graphs \(O_ k \)by parameters
• Eigenvalues and expanders
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expander graphs and their applications
• Graphs with Maximal Even Girth
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Line graphs, root systems, and elliptic geometry
• Linear programming bounds for regular graphs
• Median eigenvalues of bipartite graphs
• Median eigenvalues of bipartite planar graphs
• Minimal Regular Graphs of Girths Eight and Twelve
• On Minimal graphs of maximum even girth
• On Moore Graphs with Diameters 2 and 3
• On regular graphs and coronas whose second largest eigenvalue does not exceed 1
• On the Maximum Diameter of a Class of Distance-Regular Graphs
• On the extreme eigenvalues of regular graphs.
• On the limit points of the smallest eigenvalues of regular graphs
• On the second eigenvalue of a graph
• On the sizes of expander graphs and minimum distances of graph codes
• Pseudo-random graphs
• Ramanujan graphs
• Regular graphs whose second largest eigenvalue is at most 1
• Regular graphs with small second largest eigenvalue
• Répartition asymptotique des valeurs propres de l’opérateur de Hecke 𝑇_𝑝
• Some geometric aspects of graphs and their eigenfunctions
• Spectra of graphs
• Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3
• The Gewirtz graph: An exercise in the theory of graph spectra
• The second largest eigenvalues of regular bipartite graphs
• The uniqueness of the strongly regular graph on 77 points
• Tight estimates for eigenvalues of regular graphs
• Universally optimal distribution of points on spheres

Cited in

(13)

• Open problems in the spectral theory of signed graphs
• Graphs of degree at least \({3}\) with minimum algebraic connectivity
• On the spectrum and linear programming bound for hypergraphs
• Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey
• On the order of regular graphs with fixed second largest eigenvalue
• A spectral version of the Moore problem for bipartite regular graphs
• Largest regular multigraphs with three distinct eigenvalues
• Explicit bounds from the Alon-Boppana theorem
• A Spectral Moore Bound for Bipartite Semiregular Graphs
• The maximum valency of regular graphs with given order and odd girth
• Attainable bounds for algebraic connectivity and maximally connected regular graphs
• A relationship between the second largest eigenvalue and local valency of an edge-regular graph
• Regular graphs whose second largest eigenvalue is at most 1

This page was built for publication: Maximizing the order of a regular graph of given valency and second eigenvalue

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