Minimal Defining Sets Of Group Divisible Designs

A group divisible design(GDD)of index A is an ordered triple(X,g,A),X is a point set,g is a set of non-empty subsets of X which partition X(called groups),and A is a set of subsets of X(called blocks)such that each block intersects any given group in at most one point,and each pair of points from distinct groups appears in exactly ? blocks.Let B(?)A.If B completes uniquely to(X,g,A)and any proper subset of B can not complete uniquely to(X,g,A),then B is called a minimal defining set of(X,g,A).The minimal defining set of a design has nice application of cryptography.There have been many works which mainly focus on the critical sets of Latin squares and the minimal defining sets of t-designs.In this paper,we study the minimal defining sets of GDDs.We give some basic properties of the minimal defining sets of GDDs,and a lower bound on the size of the minimal defining set of a GDD.Given a K-GDD,(X,g,A),where |X|=v,|g|=n,kman=max{k | k ? K},gmax=max{|G| | G ? g},v-g-max>kmax-1,and k?3 for any k ? K.If B is a minimal defining set of the GDD,then |B|>v-n/kmax.We present a method for constructing a minimal defining set of a 3-GDD.Let(X,g,A)be a 3-GDD,B(?)A,L be a super-symmetric Latin square on Zw,and C be a super-symmetric partial Latin square in L.Let X*=X × Zw,g*={G × Zw | G ? g}and B*=(B(?)L)?((A\B)(?)C).If the following thrce conditions are satisfied:1.the associated configuration of(X,g,B)is uniquely generalizedly completable to that of(X,g,A),C is strongly uniquely completable to L;2.there is a(?B,hB)-trade T C A such that T ? B?{B} and hB ?w for any B ? B;3.for any(x,y:z)? C and any B ? B,there is a(?B,hB)-Latin trade R(?)L such that R?C={(x,y,z)},then B*is a minimal defining set of(X*,g*,A(?)L).Applying this construction,we obtain the minimal defining sets of a family of 3-GDDs.