Minimal perfect bicoverings of strongvstrong with block sizes two, three.pdfVIP

Minimal perfect bicoverings of Kv with block sizes two, three and four M.J. Grannell and T.S. Griggs Department of Pure Mathematics The Open University Walton Hall Milton Keynes MK7 6AA UNITED KINGDOM R.G. Stanton Department of Computer Science Univesity of Manitoba Winnipeg CANADA R3T 2N2 This is a preprint of an article accepted for publication in the Ars Combina- c toria 2004 (copyright owner as specified in the journal). Abstract We survey the status of minimal coverings of pairs with block sizes two, three and four when λ = 1, that is, all pairs from a v-set are covered exactly once. Then we provide a complete solution for the case λ = 2. 1 Introduction The covering number g (k) (v) is defined as the cardinality of the minimal λ pairwise balanced design (PBD) with largest block size k such that every pair occurs exactly λ times in the PBD. For λ = 1 we normally omit the (2) subscript. It is trivial that gλ (v) = λ v . Denoting the packing number 2 Dλ (t, k, v) as the maximum number of blocks in any t − (v, k, λ) packing, it is easily seen that g (3) (v) = Dλ (2, 3, v) + (λ v − 3Dλ (2, 3, v)); λ 2 we merely take the maximum number of triples possible and adjoin the uncovered pairs. 1 For λ = 1, this gives (i) g (3) (v) = v (v − 1)/6 all