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).
scientific article; zbMATH DE number 7379254