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

DOI10.1137/15M1030935zbMATH Open1344.05086arXiv1503.06286OpenAlexW2518216876MaRDI QIDQ2818201FDOQ2818201

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)

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.

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

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

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)

Cites Work

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

Cited In (13)

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

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)