×

More on block intersection polynomials and new applications to graphs and block designs. (English) Zbl 1228.05080

Summary: 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.

MSC:

05B05 Combinatorial aspects of block designs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Software:

DESIGN; GAP; DISCRETA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Betten, A., Schnittzahlen von Designs, Bayreuth. Math. Schr., 58 (2000), x+131 pp · Zbl 0961.05007
[2] Betten, A.; Kerber, A.; Laue, R.; Wasserman, A., Simple 8-designs with small parameters, Des. Codes Cryptogr., 15, 5-27 (1998) · Zbl 0928.05007
[3] Brouwer, A. E., Strongly regular graphs, (Colbourn, C. J.; Dinitz, J. H., Handbook of Combinatorial Designs (2007), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton), 852-868 · Zbl 1110.05320
[4] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer: Springer Berlin · Zbl 0747.05073
[5] Cameron, P. J.; Soicher, L. H., Block intersection polynomials, Bull. Lond. Math. Soc., 39, 559-564 (2007) · Zbl 1131.05014
[6] Dobcsányi, P.; Preece, D. A.; Soicher, L. H., On balanced incomplete-block designs with repeated blocks, European J. Combin., 28, 1955-1970 (2007) · Zbl 1127.05009
[7] The GAP Group, GAPhttp://www.gap-system.org/; The GAP Group, GAPhttp://www.gap-system.org/
[8] Köhler, E., Allgemeine Schnittzahlen in \(t\)-designs, Discrete Math., 73, 133-142 (1989) · Zbl 0683.05009
[9] V. Krčadinac, personal communication, Bratislava, July, 2007; V. Krčadinac, personal communication, Bratislava, July, 2007
[10] Maple, Version 9.5, 2004, http://www.maplesoft.com/; Maple, Version 9.5, 2004, http://www.maplesoft.com/
[11] McKay, B. D., Combinatorial Data: Graphs · Zbl 0386.05045
[12] McKay, B. D.; Spence, E., Classification of regular two-graphs on 36 and 38 vertices, Australas. J. Combin., 24, 293-300 (2001) · Zbl 0979.05110
[13] Mendelsohn, N. S., Intersection numbers of \(t\)-designs, (Mirsky, L., Studies in Pure Mathematics (1971), Academic Press: Academic Press London), 145-150 · Zbl 0222.05018
[14] L.H. Soicher, The DESIGNGAPhttp://designtheory.org/software/gap_design/; L.H. Soicher, The DESIGNGAPhttp://designtheory.org/software/gap_design/
[15] van Trung, T.; Wu, Q.; Mesner, D. M., High order intersection numbers of \(t\)-designs, J. Statist. Plann. Inference, 56, 257-268 (1996) · Zbl 0873.05014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.