New construction of minimal (v,3,2)-coverings
DOI:
https://doi.org/10.2298/YJOR150517017NKeywords:
covering design, covering number, steiner systemAbstract
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 the remaining blocks of (v,3,2)-covering are obtained.References
Bose, R.C., “On the construction of balanced incomplete block designs”, Annals of Eugenics, 9 (1939) 353–399.
Colbourn, C., and Rosa, A., Triple Systems, Oxford University Press, Oxford, 1999.
Cvetković, D., and Simić, S., Kombinatorika: klasichna i moderna, Naučna knjiga, Beograd, 1990.
Dai, C., Li, B., and Toulouse, M., “A Multilevel Cooperative Tabu Search Algorithm for the Covering Design Problem”, Journal of Combinatorial Mathematics and Combinatorial Computing, 68 (2009) 33–65.
Erdős, P., and Spencer, J., Probabilistic Methods in Combinatorics, Spencer Academic Press, New York, 1974.
Fort, M.K., and Hedlund, G.A., “Minimal coverings of pairs by triples”, Pacific Journal of Mathematics, 8(4) (1958) 709–719.
Gordon, D.M., La Jolla Covering Design Repository, http://www.ccrwest.org/cover.html.
Gordon, D.M., Kuperberg, G., and Patashnik, O., “New constructions for covering designs”, Journal of Combinatorial Design, 3 (4) (1995) 269–284.
Gordon, D.M., and Stinson, D.R., “Coverings” in Handbook of Combinatorial Designs, Second Edition, Chapman and Hall CRC, Boca Raton, (2007) 365–373.
Hall, M., Combinatorial Theory, John Wiley & Sons, New York, 1986.
Linder, C.C., and Rodger, C.A., Design Theory: Second Edition, Taylor & Francis Group, Boca Raton, 2009.
Nikolić, N., Grujičić, I., and Dugošija, D., “Variable neighborhood descent heuristic for covering design problem”, Electronic Notes in Discrete Mathematics, 39 (2012) 193–200.
Nikolić, N., Grujičić, I., and Mladenović, N., “A large neighbourhood search heuristic for covering designs”, IMA Journal of Management Mathematics, DOI: 10.1093/imaman/dpu003 (2014), Accepted and published online.
Nurmela, K.J., and Östergård, P.R.J., “New coverings of t-sets with (t - 1)-sets”, Journal of Combinatorial Designs, 7 (3) (1999) 217–226.
Nurmela, K.J., and Östergård, P.R.J., “Coverings of t-sets with (t - 2)-sets”, Discrete Applied Mathematics, 95 (1999) 425–437.
Rödl, V., “On a packing and covering problem”, European Journal of Combinatorics, 5 (1) (1985) 69–78.
Schönheim, J., “On coverings”, Pacific Journal of Mathematics, 14 (1964) 1405–1411.
Skolem, T., “Some remarks on the triple systems of Steiner”, Mathematica Scandinavica, 6 (1958) 273–280.
Stinson, D.R., Combinatorial Designs: Constructions and Analysis, Springer-Verlag, New York, 2004.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
