Augmenting the Delsarte bound: a forbidden interval for the order of maximal cliques in strongly regular graphs
type: Item
instance of: scholarly article
title: Augmenting the Delsarte bound: a forbidden interval for the order of maximal cliques in strongly regular graphs
zbMATH Open document ID: 1473.05323
author: Jack H. Koolen
author: Jongyook Park
author: Gary R. W. Greaves
published in: European Journal of Combinatorics
publication date: 2021-08-05T00:00:00Z
review text: Let \(\Gamma=(V,E)\) be a finite, connected, undirected and simple graph. For \(x \in V(\Gamma),\) let \(\Gamma(x)\) denote the set of vertices in \(\Gamma\) that are adjacent to \(x.\) The cardinality of \(\Gamma(x)\) is called a valency of \(x\) in \(\Gamma.\) If for all \(x \in V(\Gamma),\) we have \(k=|\Gamma(x)|\) is constant, then \(\Gamma\) is called regular with valency \(k.\) A regular graph with \(v\) vertices and valency \(k\) is called edge-regular with parameters \((v,k,\lambda)\) if any two adjacent vertices have exactly \(\lambda\) common neighbors. An edge-regular graph with parameters \((v, k, \lambda)\) is called amply regular with parameters \((v, k, \lambda,\mu)\) if any two vertices at distance \(2\) have exactly \(\mu\) common neighbors. An amply regular graph with parameters \((v, k, \lambda,\mu)\) with diameter at most \(2\) is also called strongly regular with parameters \((v, k, \lambda,\mu).\) A clique in \(\Gamma\) is a set of pairwise adjacent vertices of \(\Gamma,\) and a coclique in \(\Gamma\) is a set of pairwise non-adjacent vertices of \(\Gamma.\) The number of vertices in a clique or coclique is called the order of the clique or coclique. A clique \(C\) in \(\Gamma\) is called maximal if there is no clique in \(\Gamma\) that contains \(C\) and at least one other vertex of \(V(\Gamma)\backslash C.\) The adjacency matrix \(A = A(\Gamma)\) of \(\Gamma\) is the matrix whose rows and columns are indexed by vertices of \(\Gamma\) and the \((x, y)\)-entry is \(1\) whenever \(x\) and \(y\) are adjacent and \(0\) otherwise. The eigenvalues of \(\Gamma\) are the eigenvalues of \(A.\) If \(\Gamma\) is a strongly regular graph with parameters \((v, k, \lambda,\mu)\) and smallest eigenvalue \(-m,\) the order of a clique in \(\Gamma\) is at most \(1+\frac{k}{m}.\) It is called a Delsarte bound. A clique in \(\Gamma\) is called a Delsarte clique if its order attains the Delsarte bound. In the paper under review, the authors introduce a new method…
reviewed by: Djoko Suprijanto
Mathematics Subject Classification ID: 05E30
zbMATH DE Number: 7379254
zbMATH Keywords: cliques
zbMATH Keywords: cocliques
zbMATH Keywords: Cvetković bound
zbMATH Keywords: Hoffman bound
zbMATH Keywords: Delsarte clique
zbMATH Keywords: Delsarte bound
zbMATH Keywords: strongly regular graph
MaRDI profile type: Publication
full work available at URL: j.ejc.2021.103384
OpenAlex ID: W3180460378
cites work: Q3992965
cites work: Spectra of graphs
cites work: Q5707657
cites work: On the Koolen-Park inequality and Terwilliger graphs
cites work: Q2716030
cites work: Interlacing eigenvalues and graphs
cites work: Hoffman's ratio bound
cites work: There does not exist a distance-regular graph with intersection array \(\{80, 54,12; 1, 6, 60\}\)
cites work: Shilla distance-regular graphs
cites work: Strongly regular graphs with smallest eigenvalue -m
DOI: 10.1016/J.EJC.2021.103384
description: scientific article; zbMATH DE number 7379254