Abstract
A group covering design (GCD) is a set of mn points in n disjoint groups of size m and a collection of b k-subsets, called blocks, such that every pairset not contained in the same group occurs in at least one block. For m = 1, a GCD is a covering design [5]. Particular cases of GCD’s, namely transversal covers, covering arrays, Sperner systems etc. have been extensively studied by Poljak and Tuza [22], Sloane [24], Stevens et al. [26] and others. Cohen et al. [8], [9] and Sloane [24] have also shown applications of these designs to software testing, switching networks etc.. Determining the group covering number, the minimum value of b, for given k,m and n, in general is a hard combinatorial problem. This paper determines a lower bound for b, analogous to Schönheim lower bound for covering designs [23]. It is shown that there exist two classes of GCD’s (Theorems 15 and 18) which meet these bound. Moreover, a construction of a minimum GCD from a covering design meeting the Schönheim lower bound is given. The lower bound is further improved by one for three different classes of GCD’s. In addition, construction of group divisible designs with consecutive block sizes (Theorems 20 and 21) using properties of GCD’s are given.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. M. Assaf, An application of modified group divisible designs, J. Combin. Theory Ser. A 68 (1994), 152–168.
M. C. Bhandari, K. K. P. Chanduka and A. K. Lal, On lower bounds for covering codes, Designs, Codes and Cryptography, 15 (1998), 237–243.
A. E. Brouwer, A. Schrijver and H. Hanani, Group divisible designs with block size four, Discrete Math. 20 (1977), 1–10.
Y. Caro and Y. Raphael, Covering graphs: The covering problem solved, J. Comb. Theory, Ser. A, 83 (1998), 273–282.
K. K. P. Chanduka, “Combinatorial Designs and Covering Codes”, Ph.D. thesis, Indian Institute of Technology, Kanpur, India (January 1998).
K. K. P. Chanduka, M. C. Bhandari and A. K. Lal, Further results on q-ary covering codes, manuscript under preparation.
W. Chen and I. S. Honkala, Lower bounds for q-ary covering codes, IEEE Trans. Inform. Theory 36 (1990), 664–671.
D. M. Cohen, S. R. Dalal, J. Parelius and G. C. Patton, The combinatorial design approach to automatic test generation, IEEE software, 13 (1996), 83–88.
D. M. Cohen, S. R. Dalal, M. L. Fredman and G. C. Patton, The AETG systems: An approach to testing based on combinatorial design, IEEE Trans. Soft. Eng., 23 (1997), 437–444.
C. J. Colbourn and J. H. Dinitz, editors, “The CRC Handbook of Combinatorial Designs”, CRC Press, Boca Raton, first edition, 1996.
C. J. Colbourn and A. C. H. Ling, Pairwise balanced designs with block sizes 8, 9 and 10, J. Combin. Theory Ser. A 77 (1997), 228–245.
C. J. Colbourn, A. Rosa and D. R. Stinson, Pairwise balanced designs with block sizes three and four, Can. J. Math. 43 (1991), 673–704.
M. K. Fort and G. A. Hedlund, Minimal covering of pairs by triples, Pacific J. Math. 8 (1958), 709–719.
H. Hanani, Balanced incomplete block designs and related designs, Discrete Math. 11 (1975), 255–369.
I. S. Honkala, Modified bounds for covering codes, IEEE Trans. Inform. Theory 37 (1991), 351–365.
D. J. Kleitman and J. Spencer, Families of K-independent sets, Discrete Math. 6 (1973), 255–262.
H. Lenz, Some remarks on Pairwise balanced designs, Mitt. Math. Sem. Giessen, 165 (1984), 49–62.
A. C. H. Ling, X. Zhu, C. J. Colbourn and R. C. Mullin, Pairwise balanced designs with consecutive block sizes, Designs, Codes and Cryptography, 10 (1997), 203–222.
W. H. Mills, On the covering of pairs by quadruples I, J. Combin. Theory Ser. A 13 (1972), 55–78.
W. H. Mills, On the covering of pairs by quadruple II, J. Combin. Theory Ser. A 15 (1973), 138–166.
W. H. Mills and R. C. Mullin, Covering pairs by quintuples: The case v congruent to 3 (mod 4), J. Combin. Theory Ser. A 49 (1988), 308–322.
S. Poljak and Z. Tuza, On the maximum number of qualitatively independent partitions, J. Combin. Theory Ser. A 51 (1989), 111–116.
J. Schönheim, On coverings, Pacific J. Math. 14 (1964), 1405–1411.
N. J. A. Sloane, Covering arrays and intersecting codes, J. Combin. Designs, 1 (1993), 51–63.
B. Stevens and E. Mendelsohn, New recursive methods for transversal covers, preprint.
B. Stevens, L. Moura and E. Mendelsohn, Lower bounds for transversal covers, Designs, Codes and Cryptography, 15 (1998), 279–299.
G. Tarry, Le problème des 36 officiers, Compt. Rend. Assoc. Fr. Av. Sci. 1 (1900), 122–123; 2 (1901), 170-203.
Z. Zhang, Linear inequalities for covering codes: Part I-Pair covering inequalities, IEEE Trans. Inform. Theory 37 (1991), 573–582.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chanduka, K.K.P., Bhandari, M.C., Lal, A.K. (1999). Lower Bounds for Group Covering Designs. In: Fossorier, M., Imai, H., Lin, S., Poli, A. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 1999. Lecture Notes in Computer Science, vol 1719. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46796-3_33
Download citation
DOI: https://doi.org/10.1007/3-540-46796-3_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66723-0
Online ISBN: 978-3-540-46796-0
eBook Packages: Springer Book Archive