Linear programming bounds for regular graphs

DOI10.1007/S00373-015-1613-7zbMATH Open1332.90160arXiv1407.4562OpenAlexW1435912308MaRDI QIDQ897255FDOQ897255

Hiroshi Nozaki

Publication date: 17 December 2015

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Delsarte, Goethals, and Seidel (1977) used the linear programming method in order to find bounds for the size of spherical codes endowed with prescribed inner products between distinct points in the code. In this paper, we develop the linear programming method to obtain bounds for the number of vertices of connected regular graphs endowed with given distinct eigenvalues. This method is proved by some "dual" technique of the spherical case, motivated from the theory of association scheme. As an application of this bound, we prove that a connected $k$-regular graph satisfying $g>2d-1$ has the minimum second-largest eigenvalue of all $k$-regular graphs of the same size, where $d$ is the number of distinct non-trivial eigenvalues, and $g$ is the girth. The known graphs satisfying $g>2d-1$ are Moore graphs, incidence graphs of regular generalized polygons of order $(s,s)$, triangle-free strongly regular graphs, and the odd graph of degree $4$.

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

Recommendations

• On the spectrum and linear programming bound for hypergraphs
• A characterization of Delsarte's linear programming bound as a ratio bound
• The second eigenvalue of regular graphs of given girth
• Bounds on special subsets in graphs, eigenvalues and association schemes
• Regular graphs with girth at least 5 and small second largest eigenvalue

zbMATH Keywords

distance-regular graphgraph spectrumMoore graphRamanujan graphexpander graphlinear programming bound

Mathematics Subject Classification ID

Linear programming (90C05) Extremal set theory (05D05)

Cites Work

• Eigenvalues and expanders
• Title not available (Why is that?)
• The nonexistence of certain generalized polygons
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Problems in algebraic combinatorics
• A simple group of order 44,352,000
• Universally optimal distribution of points on spheres
• Expander graphs and their applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Gewirtz graph: An exercise in the theory of graph spectra
• On generalized hexagons and a near octagon whose lines have three points
• Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3
• On Moore Graphs with Diameters 2 and 3
• On the Polynomial of a Graph
• Minimal Regular Graphs of Girths Eight and Twelve
• Spherical codes and designs
• Some spectral and quasi-spectral characterizations of distance-regular graphs
• Title not available (Why is that?)
• Optimality and uniqueness of the \((4,10,1/6)\) spherical code
• New bounds on the number of unit spheres that can touch a unit sphere in n dimensions
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Quantum probability and spectral analysis of graphs. With a foreword by Professor Luigi Accardi.
• Uniqueness of the Projective Plane of Order Eight
• Title not available (Why is that?)
• The strong thirteen spheres problem
• Upper bounds on permutation codes via linear programming
• The kissing number in four dimensions
• Bounds on ordered codes and orthogonal arrays
• The uniqueness of the strongly regular graph on 77 points
• On Minimal graphs of maximum even girth
• Linear programming bounds for codes in grassmannian spaces
• Title not available (Why is that?)
• Codes on Euclidean spheres
• Commutative association schemes
• Designs as maximum codes in polynomial metric spaces
• 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
• On Projective Planes of Order Nine
• Uniqueness of the Projective Plane with 57 Points
• Graphs with Maximal Even Girth
• All generalized quadrangles of order 3 are known
• Generalized quadrangles of order 4. I, II

Cited In (7)

• Polynomial properties on large symmetric association schemes
• On the spectrum and linear programming bound for hypergraphs
• Graphs of degree at least \({3}\) with minimum algebraic connectivity
• A spectral version of the Moore problem for bipartite regular graphs
• A Spectral Moore Bound for Bipartite Semiregular Graphs
• Largest regular multigraphs with three distinct eigenvalues
• Maximizing the order of a regular graph of given valency and second eigenvalue

This page was built for publication: Linear programming bounds for regular graphs

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