TAILIEUCHUNG - New construction of minimal (v, 3, 2)−coverings
A (v,3,2)−covering is a family of 3-subsets of a v-set, called blocks, such that any two elements of v-set appear in at least one of the blocks. In this paper, we propose new construction of (v,3,2)−coverings with the minimum number of blocks. This construction represents a generalization of Bose’s and Skolem’s constructions of Steiner systems S(2,3,6n+3) and S(2,3,6n+1). | Yugoslav Journal of Operations Research 26 (2016), Number 4, 457–466 DOI: NEW CONSTRUCTION OF MINIMAL (v, 3, 2)−COVERINGS ´ Nebojˇsa NIKOLIC Faculty of Organizational Sciences, University of Belgrade, Serbia sigma@ Received: May 2015 / Accepted: June 2015 Abstract: A (v, 3, 2)−covering is a family of 3-subsets of a v-set, called blocks, such that any two elements of v-set appear in at least one of the blocks. In this paper, we propose new construction of (v, 3, 2)−coverings with the minimum number of blocks. This construction represents a generalization of Bose’s and Skolem’s constructions of Steiner systems S(2, 3, 6n + 3) and S(2, 3, 6n + 1). Unlike the existing constructions, our construction is direct and it uses the set of base blocks and permutation p, so by applying it to the remaining blocks of (v, 3, 2)−coverings are obtained. Keywords: Covering design, Covering number, Steiner system. MSC: 05B05, 05B07, 05B40. 1. INTRODUCTION Let v, k, and t denote natural numbers where v ≥ k ≥ t. The family of ksubsets, called blocks, chosen from a v-set, such that each t-subset is contained in at least one of the blocks, is a (v, k, t) covering design, or (v, k, t)−covering. The number of blocks is the size of the covering. The covering number C(v, k, t) is the minimum size of a (v, k, t)−covering. If each t-subset is contained in exactly one block, (v, k, t)−covering is Steiner system S(t, k, v). Covering designs and Steiner systems have application in statistical test creating, tournament scheduling, cryptography and coding, computer science, lottery systems creating etc. Covering numbers have already been studied extensively, and numerous papers have been published for particular values of v, k, and t. Nevertheless, exact values of C(v, k, t) are known only if v, k, and t are small, or in some special 458 N. Nikoli´c / New construction of minimal (v, 3, 2)−coverings cases, such as C(v, 3, 2). A large number of papers consider
đang nạp các trang xem trước
