×

Resolvable group divisible designs with large groups. (English) Zbl 1351.05179

Summary: We prove that the necessary divisibility conditions are sufficient for the existence of resolvable group divisible designs with a fixed number of sufficiently large groups. Our method combines an application of the Rees product construction with a streamlined recursion based on incomplete transversal designs. With similar techniques, we also obtain new results on decompositions of complete multipartite graphs into a prescribed graph.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B30 Other designs, configurations
05C51 Graph designs and isomorphic decomposition
PDFBibTeX XMLCite
Full Text: Link

References:

[1] J.H. Chan, Asymptotic existence results on specific graph decompositions, M.Sc. thesis, University of Victoria, 2010.
[2] S. Chowla, P. Erd˝os, and E.G. Strauss, On the maximal number of pairwise orthog onal latin squres of a given order. Canad. J. Math. 12 (1960), 204-208. · Zbl 0093.32001
[3] C.J. Colbourn and J.H. Dinitz, eds., The CRC Handbook of Combinatorial Designs, 2nd edition, CRC Press, Boca Raton, 2006.
[4] J.H. Chan, P.J. Dukes, E.R. Lamken and A.C.H. Ling, Asymptotic existence of resolvable group divisible designs. J. Combin. Des. 21 (2013) 112-126. · Zbl 1262.05016
[5] Y.M. Chee, C.J. Colbourn, A.C.H. Ling, and R.M. Wilson, Covering and packing for pairs. J. Combin. Theory Ser. A 120 (2013), 1440-1449. · Zbl 1314.05025
[6] P. Dukes and A.C.H. Ling, Asymptotic existence of resolvable graph designs. Canad. Math. Bull. 50 (2007), 504-518. · Zbl 1152.05015
[7] P. Dukes and A. Malloch, An existence theory for loopy graph decompositions. J. Combin. Des., 19 (2011), 280-289. · Zbl 1223.05227
[8] S. Furino, Y. Miao, and J. Yin, Frames and resolvable designs. CRC Press, New York, 1996. · Zbl 0855.62061
[9] G. Ge and A.C.H. Ling, Asymptotic results on the existence of 4-RGDDs and Uniform 5-GDDS. J. Combin. Des. 13 (2005), 222-237. · Zbl 1062.05023
[10] E.R. Lamken and R.M. Wilson, Decompositions of edge-colored complete graphs. J. Combin. Theory Ser. A 89 (2000), 149-200. · Zbl 0937.05064
[11] Y. Miao, Some constructions and uses of double group divisible designs. Bull. Inst. Combin. Appl. 10 (1994), 66-72. · Zbl 0807.05008
[12] H. Moh´acsy, The asymptotic existence of group divisible designs of large order with index one. J. Combin. Theory Ser. A 118 (2011), 1915-1924. · Zbl 1236.05052
[13] H. Moh´acsy, A new infinite family of group divisible t-designs with strength t > 2 and index λ, preprint.
[14] D.K. Ray-Chaudhuri and R.M. Wilson, The existence of resolvable block designs, in “A Survey of combinatorial theory” (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo.) (J.N. Srivastava, et. al., Eds.) (1973), 361-376.
[15] R. Rees, Two new direct product-type constructions for resolvable group-divisible designs. J. Combin. Des. 1 (1993) 15-26. · Zbl 0817.05008
[16] K. Ushio, Bipartite decomposition of complete multipartite graphs. Hiroshima Math. J. 11 (1981), 321-345. · Zbl 0482.05051
[17] S.A. Vanstone, Doubly resolvable designs. Discrete Math. 29 (1980), 77-86. · Zbl 0447.05010
[18] C. Wang, Resolvable holey group divisible design with block size 3. Australasian J. Combin. 39 (2007) 191-206. the electronic journal of combinatorics 23(4) (2016), #P4.24 17 · Zbl 1134.05009
[19] R.M. Wilson, Concerning the number of mutually orthogonal Latin squares. Discrete Math. 9 (1974), 181-198. · Zbl 0283.05009
[20] R.M. Wilson, An existence theory for pairwise balanced designs II: The structure of PBD-closed sets and the existence conjectures. J. Combin. Theory Ser. A 13 (1972), 246-273. · Zbl 0263.05015
[21] R.M. Wilson, An existence theory for pairwise balanced designs III: Proof of the existence conjectures. J. Combin. Theory Ser. A 18 (1975), 71-79. · Zbl 0295.05002
[22] R.M. Wilson, Constructions and uses of pairwise balanced designs, in Mathematisch Centre Tracts, vol 55, Mathematisch Centrum, Amersterdam, 1974, 18-41. · Zbl 0312.05010
[23] R.M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph. Congressus Numerantium XV (1975), 647-659. · Zbl 0322.05116
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.