We use the notation K_v to denote the complete graph of v vertice. The notationK_r×K_c stands for the Cartersian product of K_r and K_r in which two distinct vertices(u, v) and (u′, v′) are joined by exactly one edge if and only if u=u′or v=v′. An r×cgrid-block design denoted by (v, r×c, 1)-GBD is a pair (X, A), where X is the vertexset of K_v, A is a collection of subgraphs of K_v, each being isomorphic to K_r×K_c andcalled r×c grid-block, which form a partition of the edge set of K_v. The notion ofr×c grid-block design was introduced by Hwang associated with its application in theDNA library screening. Scine then, the problem of the existence of the r×c grid-blockdesign has attracted considerable attention. The existence of a (v, 2×2, 1)-GBD isknown in terms of a 4-cycle system. J. E. Carter, H. L. Fu, Y. Mutoh and othersresolve the problems of the existence of r×c grid-block designs, where r, c are in{(2, 3), (2, 4), (3, 3)}. For large values of r and c, as the structures are complex, it is adifficult task to construct the corresponding r×c grid-block designs, and there are noliteratures reported. In this paper, we pay attention to the case for r=2 and c=5,and prove that the necessary conditions of the existence of this r×c grid-block designare also sufficient. Namely a (v, 2×5, 1)-GBD exists, if and only if v≡1(mod 25).
|