Augmenting the Delsarte bound: a forbidden interval for the order of maximal cliques in strongly regular graphs
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 for restricting the order of maximal clique in a strongly regular graph based on its parameters. As a consequence, they show that if a strongly regular graph contains a Delsarte clique, then the parameter \(\mu\) is either small or large (Proposition 3.3). As a consequence, the paper shows the nonexistence of strongly regular graphs with parameters \((v,k,\lambda,\mu)\) (Theorem 4.4).
- Hoffman's ratio bound
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 43547 (Why is no real title available?)
- scientific article; zbMATH DE number 2232233 (Why is no real title available?)
- Interlacing eigenvalues and graphs
- On the Koolen-Park inequality and Terwilliger graphs
- Shilla distance-regular graphs
- Spectra of graphs
- Strongly regular graphs with smallest eigenvalue -m
- There does not exist a distance-regular graph with intersection array \(\{80, 54,12; 1, 6, 60\}\)
- On the clique number of a strongly regular graph
- There does not exist a strongly regular graph with parameters \((1911, 270, 105, 27)\)
- Asymptotic Delsarte cliques in distance-regular graphs
- Delsarte set graphs with small \(c_{2}\)
- A structure theory for regular graphs with fixed smallest eigenvalue
- Non-existence of two infinite families of strongly regular graphs
- Delsarte clique graphs
This page was built for publication: Augmenting the Delsarte bound: a forbidden interval for the order of maximal cliques in strongly regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048358)
