More on block intersection polynomials and new applications to graphs and block designs

摘要

The concept of intersection numbers of order r for t-designs is generalized to graphs and to block designs which are not necessarily t-designs. These intersection numbers satisfy certain integer linear equations involving binomial coefficients, and information on the non-negative integer solutions to these equations can be obtained using the block intersection polynomials introduced by P.J. Cameron and the present author. The theory of block intersection polynomials is extended, and new applications of these polynomials to the studies of graphs and block designs are obtained. In particular, we obtain a new method of bounding the size of a clique in an edge-regular graph with given parameters, which can improve on the Hoffman bound when applicable, and a new method for studying the possibility of a graph with given vertex-degree sequence being an induced subgraph of a strongly regular graph with given parameters.