Font Size: a A A

Constructions Of Generalized Kirkman Squares

Posted on:2015-08-13Degree:MasterType:Thesis
Country:ChinaCandidate:J DuFull Text:PDF
GTID:2180330473950101Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Let k, λ, r, and v be positive integers. A generalized Kirkman square with block size k, index λ, replication number r, and v elements, GKSk(v; 1, λ; r), is an r x r array S defined on a v-set V such that(1) each cell of S is either empty or contains a κ-set of V,(2) every element of V occurs once in each row and column of S,(3) each 2-subset of V is contained in at most λ κ-sets of S.A generalized Kirkman, GKS2(u,1,1; r)), is just a Howell design H(r, u). A GKS2(u; 1,1; u-1) is a Room square of order u-1. Obviously, a Howell design is a generalization of a Room square, and a generalized Kirkman square is a gener-alization of a Howell design. When r=(λ(u-1)/(k-1) a generalized Kirkman square is a Kirkman square, and denoted by KSk(u;1,λ). As everyone knows, a doubly resolv-able (v, k,λ)-BIBD is just a Kirkman square. There are tight connections between generalized Kirkman squares and doubly resolvable packing designs. Doubly re-solvable GDDs are one kind of generalized Kirkman squares. A lot of work was done about generalized Kirkman squares. In 1975, Mullin and Wallis established the spectrum of Room squares. The existence of Howell designs has been completely determined by Stinson et al. in 1984. In 2008, Abel et.al. established almost the spectrums of KSs(u; 1, 1)s and KS3(u; 1,2)s. In 2013, Abel et al. furthermore studied the problem for the existence of doubly resolvable nearly Kirkman triple systems DRNKTS(u)s (i.e., GKS3(u;1,1; (u-2)/2)s). In this paper, we are interested in the constructions of generalized Kirkman squares. We will discuss the existence of GKS3(4u; 1,1,2(u-1))s and GKS3(6u; 1,1,Z(u-1))s, which are doubly resolvable GDDs,3-DRGDDs of types 4u and 6u.Section 2 uses standard "starter-adder" method to construct directly some new 3-DRGDDs of types 4u and 6u with small order u, which are foundation for our later recursive constructions.Section 3 describes a few new constructions for frames and summarizes some known results on frames with block size 3 and types 2t,4t, and 6t.Section 4 first establishes the recursive constructions for 3-DRGDDs by using frames, GDDs and PBDs. Then applying these recursive constructions shows the ex-istence of two kinds generalized Kirkman squares. Namely, there exist a 3-DRGDD of type 4u for u≥3 and u=0 (mod 3) with 17 possible exceptions, and a 3-DRGDD of type 6u for u≥3 with 31 possible exceptions.In Section 5, we discuss the tight connections between generalized Kirkman squares and doubly constant weight codes, constant composition codes. As appli-cations of generalized Kirkman squares, we obtain some new classes of codes.Section 6 gives some concluding remarks and problems for further research.
Keywords/Search Tags:Generalized Kirkman square, Group divisible design, Doubly re- solvable, Frame, Starter, Adder
PDF Full Text Request
Related items