Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647117 | Discrete Mathematics | 2016 | 9 Pages |
In this paper, we are interested in minimizing the sum of block sizes in a pairwise balanced design, where there are some constraints on the size of one block or the size of the largest block. For every positive integers n,mn,m, where m≤nm≤n, let S(n,m)S(n,m) be the smallest integer ss for which there exists a PBD on nn points whose largest block has size mm and the sum of its block sizes is equal to ss. Also, let S′(n,m)S′(n,m) be the smallest integer ss for which there exists a PBD on nn points which has a block of size mm and the sum of it block sizes is equal to ss. We prove some lower bounds for S(n,m)S(n,m) and S′(n,m)S′(n,m). Moreover, we apply these bounds to determine the asymptotic behaviour of the sigma clique partition number of the graph Kn−KmKn−Km, the Cocktail party graphs and complement of paths and cycles.