TY - JOUR
T1 - Halving transversal designs
AU - Fronček, Dalibor
AU - Meszka, Mariusz
PY - 2000
Y1 - 2000
N2 - A factor H of a transversal design TD(k, n) = (V, script G sign, ℬ), where V is the set of points, script G sign the set of groups of size n and ℬ the set of blocks of size k, is a triple (V, script G sign, script D) such that script D is a subset of ℬ. A halving of a TD(k, n) is a pair of factors Hi = (V, script G sign, script Di), i = 1, 2 such that script Di ∪ script D2 = ℬ, script D1 ∩ script D2 = Ø and H1 is isomorphic to H2. A path of length q is a sequence x0,x1, . . . ,xq of points such that for each i = 1,2, . . . , q the points xi-1 and xi belong to a block Bi and no point appears more than once. The distance between points x and y in a factor H is the length of the shortest path from x to y. The diameter of a connected factor H is the maximum of the set of distances among all pairs of points of H. We prove that a TD(3, n) is halvable into isomorphic factors of diameter d only if d = 2, 3, 4, or ∞ and we completely determine for which values of n there exists such a halvable TD(3, n). We also show that if any group divisible design with block size at least 3 is decomposed into two factors with the same finite diameter d, then d ≤ 4.
AB - A factor H of a transversal design TD(k, n) = (V, script G sign, ℬ), where V is the set of points, script G sign the set of groups of size n and ℬ the set of blocks of size k, is a triple (V, script G sign, script D) such that script D is a subset of ℬ. A halving of a TD(k, n) is a pair of factors Hi = (V, script G sign, script Di), i = 1, 2 such that script Di ∪ script D2 = ℬ, script D1 ∩ script D2 = Ø and H1 is isomorphic to H2. A path of length q is a sequence x0,x1, . . . ,xq of points such that for each i = 1,2, . . . , q the points xi-1 and xi belong to a block Bi and no point appears more than once. The distance between points x and y in a factor H is the length of the shortest path from x to y. The diameter of a connected factor H is the maximum of the set of distances among all pairs of points of H. We prove that a TD(3, n) is halvable into isomorphic factors of diameter d only if d = 2, 3, 4, or ∞ and we completely determine for which values of n there exists such a halvable TD(3, n). We also show that if any group divisible design with block size at least 3 is decomposed into two factors with the same finite diameter d, then d ≤ 4.
KW - Complete multipartite graphs
KW - Diameter
KW - Isomorphic factors
KW - Self complementary factors
KW - Transversal designs
UR - http://www.scopus.com/inward/record.url?scp=27844560792&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=27844560792&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1520-6610(2000)8:2<83::AID-JCD2>3.0.CO;2-V
DO - 10.1002/(SICI)1520-6610(2000)8:2<83::AID-JCD2>3.0.CO;2-V
M3 - Article
AN - SCOPUS:27844560792
SN - 1063-8539
VL - 8
SP - 83
EP - 99
JO - Journal of Combinatorial Designs
JF - Journal of Combinatorial Designs
IS - 2
ER -