Linear programming bounds for regular graphs

DOI10.1007/S00373-015-1613-7MaRDI QIDQ897255zbMATH OpenOpenAlexFDO

Authors Hiroshi Nozaki

Publication date 17 December 2015

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

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

zbMATH Keywords

distance-regular graphgraph spectrumMoore graphRamanujan graphexpander graphlinear programming bound

Mathematics Subject Classification ID

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

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

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

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

Cited in

(7)

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

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)