Halving transversal designs

Dalibor Fronček, Mariusz Meszka

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)83-99
Number of pages17
JournalJournal of Combinatorial Designs
Volume8
Issue number2
DOIs
StatePublished - 2000

Keywords

  • Complete multipartite graphs
  • Diameter
  • Isomorphic factors
  • Self complementary factors
  • Transversal designs

Fingerprint

Dive into the research topics of 'Halving transversal designs'. Together they form a unique fingerprint.

Cite this