The Existence Of Several Classes Of Grid Block Designs

Let Kv be a complete graph of v vertice. Kr×Kc is a Cartersian product of Kr and Kr,also called Kr×Kc-grid block,satisfying any two different vertices(a1,b1)and (a2, b2)are joined if and only if a1= a2 or b1= b2 A (Kr×Kc, A)-design of order v, denoted by GD(v; Kr×Kc, A),is a pair (X, A) where Xisthe vertice set of ofKv,A is a set of Kr×Kc grid blocks such that each edge of Kv occurs exactly λ times in Kr×Kc-grid blocks.F.Hwang et al, Taiwanese researchers, first defined grid block designs and also illustrated their applications in DNA library screening. Since then, the problems on the existence of grid block designs have absorbed much attention.Making use of the theories and methods from algebraic, finite fields and graph theory et al, we analysis deeply the structures of different kinds of grid block designs. With the aid of computer, we construct a lot of grid block designs with small parameters. Combining the use of the methods of producing grid block designs with any index and PBD theory from combinatorial design theory, we finally establish the existence of several classes of grid block designsFu solved the existence of GD(v; K3×K3,1) in 2004.In this paper, we first completely solved the existence of GD(v;K3×K3,λ) for any integer λ≥1.We have proved that a GD(v; K3×K3, λ) exists if and only if λ(v-1)≡0(mod 4) and λv(v-1)= 0(mod 36).Next we study the existence of K2×K4-GDD of type gu. We prove that a K2×K4-GDD of type gu exsits if and only if g(u-1)= 0 (mod 4) and g2u(u-1)≡ 0(mod 32) with finite possible exceptions. As an application of this kind of grid block designs, we obtain a class of optimal K2 x K4 grid block packings.With the growth of r and c,it will be very difficult to solve the existence of GD(v; Kr× Kc, λ).Wang et al have proved that the necessary conditions of a GD(v; K2×K6, λ) are also sufficient when λ=1.In the end of this paper,we provide a class of GD(v; K2×K6; 2). We have proved that if v≡1 (mod 32),then a GD(v; K2×K6,2) exists.