# Group Divisible Designs with Two Associate Classes andλ2=1

Authors: Nittiya Pabhapote; Narong Punnim
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

The original classiffcation of PBIBDs defined group divisible designs GDD(v=v1+v2+⋯+vg,g,k,λ1,λ2) with λ1≠0. In this paper, we prove that the necessary
conditions are suffcient for the existence of the group divisible designs with two groups
of unequal sizes and block size three with λ2=1.


---

## Body

## 1. Introduction

Apairwise balanced design is an ordered pair (S,ℬ), denoted PBD(S,ℬ), where S is a finite set of symbols, and ℬ is a collection of subsets of S called blocks, such that each pair of distinct elements of S occurs together in exactly one block of ℬ. Here |S|=v is called the order of the PBD. Note that there is no condition on the size of the blocks in ℬ. If all blocks are of the same size k, then we have a Steiner systemS(v,k).  A PBD with index λ can be defined similarly; each pair of distinct elements occurs in λ blocks. If all blocks are same size, say k, then we get a balanced incomplete block design BIBD(v,b,r,k,λ). In other words, a BIBD(v,b,r,k,λ) is a set S of v elements together with a collection of b  k-subsets of S, called blocks, where each point occurs in r blocks, and each pair of distinct elements occurs in exactly λ blocks (see [1–3]).Note that in a BIBD(v,b,r,k,λ), the parameters must satisfy the necessary conditions(1)
vr=bk and(2)
λ(v-1)=r(k-1).With these conditions, a BIBD(v,b,r,k,λ) is usually written as BIBD(v,k,λ).Agroup divisible design GDD(v=v1+v2+⋯+vg,g,k,λ1,λ2) is an ordered triple (V,G,ℬ), where V is a v-set of symbols, G is a partition of V into g sets of size v1,v2,…,vg, each set being called group, and ℬ is a collection of k-subsets (called blocks) of V, such that each pair of symbols from the same group occurs in exactly λ1 blocks, and each pair of symbols from different groups occurs in exactly λ2 blocks (see [1, 2, 4]). Elements occurring together in the same group are called first associates, and elements occurring in different groups we called second associates. We say that the GDD is defined on the set V. The existence of such GDDs has been of interest over the years, going back to at least the work of Bose and Shimamoto in 1952 who began classifying such designs [5]. More recently, much work has been done on the existence of such designs when λ1=0 (see [6] for a summary), and the designs here are called partially balanced incomplete block designs (PBIBDs) of group divisible type in [6]. The existence question for k=3 has been solved by Fu and Rodger [1, 2] when all groups are the same size.In this paper, we continue to focus on blocks of size 3, solving the problem when the required designs having two groups of unequal size, namely, we consider the problem of determining necessary conditions for an existence of GDD(v=m+n,2,3,λ1,λ2) and prove that the conditions are sufficient for some infinite families. Since we are dealing on GDDs with two groups and block size 3, we will use GDD(m,n;λ1,λ2) for GDD(v=m+n,2,3,λ1,λ2) from now on, and we refer to the blocks as triples. We denote (X,Y;ℬ) for a GDD(m,n;λ1,λ2) if X and Y are m-set and n-set, respectively. Chaiyasena, et al. [7] have written a paper in this direction. In particular, they have completely solved the problem of determining all pairs of integers (n,λ) in which a GDD(1,n;1,λ) exists. We continue to investigate in this paper all triples of integers (m,n,λ) in which a GDD(m,n;λ,1) exists. We will see that necessary conditions on the existence of a GDD(m,n;λ1,λ2) can be easily obtained by describing it graphically as follows.LetλKv denote the graph on v vertices in which each pair of vertices is joined by λ edges. Let G1 and G2 be graphs. The graph G1∨λG2 is formed from the union of G1 and G2 by joining each vertex in G1 to each vertex in G2 with λ edges. A  G-decomposition of a graph H is a partition of the edges of H such that each element of the partition induces a copy of G. Thus the existence of a GDD(m,n;λ1,λ2) is easily seen to be equivalent to the existence of a K3-decomposition of λ1Km∨λ2λ1Kn. The graph λ1Km∨λ2λ1Kn is of order m+n and size λ1[(m2)+(n2)]+λ2mn. It contains m vertices of degree λ1(m-1)+λ2n and n vertices of degree λ1(n-1)+λ2m. Thus the existence of a K3-decomposition of λ1Km∨λ2λ1Kn implies(1)
3∣λ1[(m2)+(n2)]+λ2mn, and(2)
2∣λ1(m-1)+λ2n and 2∣λ1(n-1)+λ2m.


## 2. Preliminary Results

We will review some known results concerning triple designs that will be used in the sequel, most of which are taken from [3].Theorem 2.1.
Letv be a positive integer. Then there exists a  BIBD(v,3,1) if and only if v≡1or3(mod6).A BIBD(v,3,1) is usually called Steiner triple system and is denoted by STS(v). Let (V,ℬ) be an STS(v). Then the number of triples b=|ℬ|=v(v-1)/6. A parallel class in an STS(v) is a set of disjoint triples whose union is the set V. A parallel class contains v/3 triples, and, hence, an STS(v) having a parallel class can exist only when v≡3(mod6). When the set ℬ can be partitioned into parallel classes, such a partition ℛ is called a resolution of the STS(v), and the STS(v) is called resolvable. If (V,ℬ) is an STS(v), and ℛ is a resolution of it, then (V,ℬ,ℛ) is called a Kirkman triple system, denoted by KTS(v), with (V,ℬ) as its underlying STS. It is well known that a KTS(v) exists if and only if v≡3(mod6). Thus if (V,ℬ,ℛ) is a KTS(v), then ℛ contains (v-1)/2 parallel classes.Theorem 2.2.
There exists a  PBD(6k+5) with one block of size 5 and 6k2+9k blocks of size 3.Example 2.3.
LetS={1,2,3,…,11}. Then PBD(11) is an ordered pair (S,ℬ), where ℬ contains the following blocks:
(2.1){1,2,3,4,5}{2,6,9}{3,7,8}{4,8,11}{1,6,7}{2,7,11}{3,9,10}{5,6,8}{1,8,9}{2,8,10}{4,6,10}{5,7,10}{1,10,11}{3,6,11}{4,7,9}{5,9,11}.Afactor of a graph G is a spanning subgraph. An r-factor of a graph is a spanning r-regular subgraph, and an r-factorization is a partition of the edges of the graph into disjoint r-factors. A graph G is said to be  r-factorable if it admits an r-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of an r-regular graph G is a set of 1-factors which partition the egde set of G. The following results are well known.Theorem 2.4.
The complete graphK2n is 1-factorable, K2n+1 is 2-factorable, and K3n+1 is 3-factorable.The following results on existence ofλ-fold triple systems are well known (see,  e.g., [3]).Theorem 2.5.
Letn be a positive integer. Then a  BIBD(n,3,λ) exists if and only if λ and n are in one of the following cases:
(a)
λ≡0(mod6) and n≠2,(b)
λ≡1or5(mod6) and n≡1or3(mod6),(c)
λ≡2or4(mod6) and n≡0or1(mod3), and(d)
λ≡3(mod6) and n is odd.The results of Chaiyasena, et al. [7] will be useful, and we will state their results as follows.Theorem 2.6.
Letv be a positive integer with v≥3. The  spectrum  of λ, denoted S1,v is defined as
(2.2)S1,v={λ:aGDD(1,v;1,λ)exists}.
Then(a)
S1,v={1,3,5,…,v-1} if v≡0(mod6),(b)
S1,v={6,12,18,…,v-1} if v≡1(mod6),(c)
S1,v={1,7,13,…,v-1} if v≡2(mod6),(d)
S1,v={2,4,6,…,v-1} if v≡3(mod6),(e)
S1,v={3,9,15,…,v-1} if v≡4(mod6), and(f)
S1,v={4,10,16,…,v-1} if v≡5(mod6).The following notations will be used throughout the paper for our constructions.(1)
LetT={x,y,z} be a triple and a∉T. We use a*T for three triples of the form {a,x,y},{a,x,z},{a,y,z}. If 𝒯 is a set of triples, then a*𝒯 is defined as {a*T:T∈𝒯}.(2)
LetG=〈V(G),E(G)〉 be a graph. If u,v∈V(G), e=uv∈E(G), and a∉V(G), then we use a+e for the triple {a,u,v}. We further use a+E(G) for the collection of triples a+e for all e∈E(G). In other words,
(2.3)a+E(G):={a+e:e∈E(G)}.
In particular, if ℱ={x1y1,x2y2,…,xnyn} is a 1-factor of K2n and a is not in the vertex set of K2n, then
(2.4)a+F={{a,x1,y1},{a,x2,y2},…,{a,xn,yn}}.
If Cm:x1,x2,…,xm+1=x1 is a cycle in Kn, then
(2.5)a+Cm={{a,x1,x2},{a,x2,x3},…,{a,xm-1,xm},{a,xm,x1}}.
Also if G is a 2-regular graph and a∉V(G), then a+E(G) forms a collection of triples such that for each u∈V(G), there are exactly two triples in a+E(G) containing a and u. In general if G is an r-regular graph and a∉V(G), then a+E(G) forms a collection of triples such that for each u∈V(G), there are exactly r triples in a+E(G) containing a and u.(3)
LetV be a v-set. We use K(V) for the complete graph Kv on the vertex set V.(4)
LetV be a v-set. Let STS(V) be defined as
(2.6)STS(V)={B:(V,B)isanSTS(v)}.
KTS(V) and BIBD(V,3,λ) can be defined similarly, that is,
(2.7)KTS(V)={B:(V,B)isaKTS(v)},BIBD(V,3,λ)={B:(V,B)isaBIBD(v,3,λ)}.
Let X and Y be disjoint sets of cardinality m and n, respectively. We define GDD(X,Y;λ1,λ2) as
(2.8)GDD(X,Y;λ1,λ2)={B:(X,Y;B)isaGDD(m,n;λ1,λ2)}.(5)
When we say thatℬ is a collection of subsets (blocks) of a v-set V, ℬ may contain repeated blocks. Thus, “∪” in our construction will be used for the union of multisets.


## 3. GDD(m,n;λ,1)

Letλ be a positive integer. We consider in this section the problem of determining all pairs of integers (m,n) in which a GDD(m,n;λ,1) exists. Recall that the existence of GDD(m,n;λ,1) implies 3∣λ[m(m-1)+n(n-1)]+2mn, 2∣λ(m-1)+n and 2∣λ(n-1)+m. Let (3.1)S(λ):={(m,n):aGDD(m,n;λ,1)exists}.By solving systems of linear congruences, we obtain the following necessary conditions.Lemma 3.1.
Lett be a nonnegative integer.
(a)
If(m,n)∈S(6t+1), then there exist nonnegative integers h and k such that {m,n}∈{{6k+1,6h+2},{6k+1,6h+6},{6k+3,6h+4},{6k+3,6h+6},{6k+5,6h+2},{6k+5,6h+4}}.(b)
If(m,n)∈S(6t+2), then there exist nonnegative integers h and k such that {m,n}∈{{6k+6,6h+4},{6k+6,6h+6}}.(c)
If(m,n)∈S(6t+3), then there exist nonnegative integers h and k such that {m,n}∈{{6k+1,6h+6},{6k+3,6h+2},{6k+3,6h+4},{6k+3,6h+6},{6k+5,6h+6}}.(d)
If(m,n)∈S(6t+4), then there exist nonnegative integers h and k such that {m,n}∈{{6k+2,6h+2},{6k+2,6h+4},{6k+6,6h+4},{6k+6,6h+6}}.(e)
If(m,n)∈S(6t+5), then there exist nonnegative integers h and k such that {m,n}∈{{6k+1,6h+6},{6k+3,6h+4},{6k+3,6h+6}}.(f)
If(m,n)∈S(6t+6), then there exist nonnegative integers h and k such that {m,n}∈{{6k+6,6h+2},{6k+6,6h+4},{6k+6,6h+6}}.In order to obtain sufficient conditions on an existence of GDD(m,n;λ,1), we first observe the following facts.  (1)
LetX and Y be two disjoint sets of size m and n, respectively. Then STS(X∪Y)≠∅ if and only if GDD(X,Y;1,1)≠∅.(2)
LetX and Y be two disjoint sets of size m and n; respectively, and let λ∈{2,3,4,5,6}. Then GDD(X,Y;λ,1)≠∅ if STS(X∪Y)≠∅, BIBD(X,3,λ-1)≠∅, and BIBD(Y,3,λ-1)≠∅.Thus, we have the following results.Lemma 3.2.
Leth and k be nonnegative integers. Then
(a)
(6k+1,6h+6),(6k+6,6h+1),(6k+3,6h+6),(6k+6,6h+3),(6k+3,6h+4),(6k+4,6h+3),
(6k+1,6h+2),(6k+2,6h+1),(6k+5,6h+2),(6k+2,6h+5),(6k+5,6h+4),
(6k+4,6h+5)∈S(1),(b)
(6k+1,6h+6),(6k+6,6h+1),(6k+3,6h+6),(6k+6,6h+3),(6k+3,6h+4),(6k+4,6h+3)∈S(3), and(c)
(6k+1,6h+6),(6k+6,6h+1),(6k+3,6h+6),(6k+6,6h+3),(6k+3,6h+4),
(6k+4,6h+3)∈S(5).Lemma 3.3.
Leth and k be nonnegative integers. Then,
(a)
(6k+6,6h+6)∈S(2) and(b)
(6k+6,6h+4),(6k+4,6h+6)∈S(2).Proof.
(a) We first consider an existence of GDD(6,6;2,1), where the groups are X={1,2,3,4,5,6} and Y={a1,a2,…,a6}. Let ℱ={ℱ1,ℱ2,…,ℱ5} be a 1-factorization of K(X). Let ℬ1=⋃i=15(ai+ℱi), ℬ2∈STS(X∪{a6}), and ℬ3∈BIBD(Y,3,2). Then (X,Y;ℬ) forms a GDD(6,6;2,1), where ℬ=ℬ1∪ℬ2∪ℬ3. Thus (6,6)∈S(2).
LetX and Y be two sets of size 6k+6 and 6h+6, respectively. Suppose that k≤h and h≥1. Let a1,a2,a3∈Y and let Y′=Y-{a1,a2,a3}. Thus, KTS(Y′)≠∅. Let ℬ1∈KTS(Y′) with 𝒫1,𝒫2,…,𝒫3h+1 as its parallel classes. Since STS(X∪Y′) and STS(X∪{a1,a2,a3}) are not empty, there exist ℬ2∈STS(X∪Y′) and ℬ3∈STS(X∪{a1,a2,a3}). We now let ℬ as
(3.2)(⋃i=13(ai*Pi))∪(⋃i=43h+1Pi)∪B2∪B3∪{{a1,a2,a3}}.
Thus, (X,Y;ℬ) forms a GDD(6k+6,6h+6;2,1) and (6k+6,6h+6)∈S(2).
(b) LetX and Y be two sets of size 6k+6 and 6h+4, respectively, a∈Y and let Y′=Y-{a}. Choose ℬ1∈KTS(Y′) with 𝒫1,𝒫2,…,𝒫3h+1 as its parallel classes. Since STS(X∪Y′) and STS(X∪{a}) are not empty, there exist ℬ2∈STS(X∪Y′) and ℬ3∈STS(X∪{a}). We now let ℬ as
(3.3)B2∪B3∪(a*P1)∪(⋃i=23h+1Pi).
Thus, (X,Y;ℬ) forms a GDD(6k+6,6h+4;2,1) and (6k+6,6h+4)∈S(2).
Therefore, the proof is complete.Part of the proof of the following lemma is based on an existence of GDD(4,4;2,3) which we now construct. Let A={a,b,c,d} and B={1,2,3,4}. Then it is easy to check that F∈GDD(A,B;2,3), where F={{1,a,b},{1,a,c},{1,a,d},{2,b,c},{2,b,d},{2,b,a},{3,c,d},{3,c,a},{3,c,b},{4,d,a}, {4,d,b},{4,d,c},{a,2,3},{a,2,4},{a,3,4},{b,1,3},{b,1,4},{b,3,4},{c,1,2},{c,1,4}, {c,2,4},{d,1,2},{d,1,3},{d,2,3}}.Lemma 3.4.
Leth and k be nonnegative integers. Then(3.4)(6k+2,6h+3),(6k+3,6h+2),(6k+5,6h+6),(6k+6,6h+5)∈S(3)Proof.
Case 1.
LetXk be a (6k+2)-set containing a1,a2, and Yh be a (6h+3)-set containing 1,2,3.
Subcase 1 (k = 0).
Letℬ0={{1,2,3},{1,2,3},{1,2,3},{1,a1,a2},{2,a1,a2},{3,a1,a2}}, and we can see that ℬ0∈GDD(X0,Y0;3,1). Suppose that h≥1. Since X0∪Yh is a set of size 6h+5, it follows by Theorem 2.2, that there exists a PBD(6h+5), (X0∪Yh,ℬ1), in which {1,2,3,a1,a2}∈ℬ1 and 6h2+9h triples in ℬ1. Let ℬ1′=ℬ1-{{1,2,3,a,b}}. Since Yh is a (6h+3)-set, it follows, by Theorem 2.5(c), that BIBD(Yh,3,2)≠∅. Let ℬ2∈BIBD(Yh,3,2). It is easy to see that (X0,Yh;ℬ) forms a GDD(2,6h+3;3,1), where
(3.5)B=B0∪B1′∪B2.
Subcase 2 (k = 1).
A GDD(8,6h+3;3,1) can be constructed as follows. Let X=A∪B, where A and B are sets of size four. It is clear that STS(Yh), STS(A∪Yh), and STS(B∪Yh) are not empty. It has been shown above that GDD(A,B;2,3) is not empty. We now choose ℬ1∈STS(Yh), ℬ2∈STS(A∪Yh), ℬ3∈STS(B∪Yh), and ℬ4∈GDD(A,B;2,3), and let ℬ=ℬ1∪ℬ2∪ℬ3∪ℬ4. Then, (X,Yh;ℬ) form a GDD(8,6h+3;3,1).
Subcase 3 (k = 2).
We first consider the existence of GDD(4,10;2,3) with A={0,1,2,…,9} and B={a0,a1,a2,a3}. Let K(A) be the complete graph of order 10 with A as its vertex set. It is well known that K10 is 1-factorable. In other words, K10 can be decomposed as a union of nine edge-disjoint 1-factors. Consequently, K10 can be decomposed as a union of three edge-disjoint 3-factors. Also, K10 can be decomposed as a union of 10C3 and a 3-factor: ten triples {{x,x+1,x+3}:x=0,1,…,9} and a 3-factor ℱ0 of K10, where
(3.6)E(F0)=⋃i=09{{i,i+4},{i,i+5},{i,i+6}},
reducing arithmetic operations (mod10). Therefore, 2K10 can be decomposed as a union of 10C3 and four 3-factors.
Letℱ1,ℱ2,ℱ3 be a 3-factorization of K10 and 10C3 and ℱ0 as described above. Then (A,B;ℬ) forms a GDD(10,4;2,3), where the collection
(3.7)B={10C3}∪⋃i=03(ai+Fi)∪B1
with ℬ1={{a0,a1,a2},{a1,a2,a3},{a2,a3,a0},{a3,a0,a1}}.
A GDD(14,6h+3;3,1) can be constructed as follows. Let X=A∪B, where A and B are sets of size ten and four, respectively. It is clear that STS(Yh), STS(A∪Yh), and STS(B∪Yh) are not empty. It has been shown above that GDD(A,B;2,3) is not empty. We now choose ℬ1∈STS(Yh), ℬ2∈STS(A∪Yh), ℬ3∈STS(B∪Yh), and ℬ4∈GDD(A,B;2,3) and let ℬ=ℬ1∪ℬ2∪ℬ3∪ℬ4. Then (X,Yh;ℬ) form a GDD(14,6h+3;3,1).
Subcase 4 (k ≥ 3).
LetA={a1,a2,a3,a4,a5}. Suppose that A⊆Xk and X′=Xk-A. Since X′ is a (6k-3)-set, it follows that STS(X′)≠∅ and KTS(X′)≠∅. Choose ℬ1∈ STS(X′) and let 𝒦∈KTS(X′) with 𝒫1,𝒫2,…,𝒫3k-2 as its parallel classes. Let ℬ2=⋃i=15(ai*𝒫i)∪⋃i=63k-1𝒫i. Since Xk∪Yh is a set of size 6(k+h)+5, we choose a PBD(6(k+h)+5), (Xk∪Yh,ℬ3), as in Theorem 2.2 in which A∈ℬ3. Let ℬ3′=B3-{A}. Since A is a 5-set and Yh is a (6h+3)-set, it follows, by Theorem 2.5(c) and (d), that there exist ℬ4∈BIBD(5,3,3) and ℬ5∈BIBD(Yh,3,2). Thus, we can see that (Xk,Yh;ℬ) forms a GDD(6k+2,6h+3;3,1), where
(3.8)B=B1∪B2∪B3′∪B4∪B5.
Case 2.
We now suppose thatX and Y be sets of size 6k+5 and 6h+6, respectively. We suppose further that a∈X and X′=X-{a}. By Lemma 3.3(b), we have GDD(X′,Y;2,1)≠∅. Choose ℬ1∈GDD(X′,Y;2,1) and ℬ2∈STS(Y∪{a}). By Theorem 2.6(e) that GDD({a},X′;1,3)≠∅. Choose ℬ3∈GDD({a},X′;1,3). Let ℬ=ℬ1∪ℬ2∪ℬ3, and it is easy to see that ℬ∈GDD(X,Y;3,1).
Thus,(6k+5,6h+6)∈S(3).Lemma 3.5.
Leth and k be nonnegative integers. Then
(a)
(6k+6,6h+6)∈S(4) and (6k+6,6h+6)∈S(6),(b)
(6k+6,6h+4),(6k+4,6h+6)∈S(4) and (6k+6,6h+4),(6k+4,6h+6)∈S(6),(c)
(6k+2,6h+2) withh,knot both zero, (6k+2,6h+4),(6k+4,6h+2)∈S(4), and(d)
(6k+6,6h+2),(6k+2,6h+6)∈S(6).Proof.
The proofs of (a) and (b) follow from the results of Lemma3.3(a), and (b), respectively, and Theorem 2.5(c).
(c) We have the following cases.
Case 1 (6k + 2, 6h + 2).
LetXk be a (6k+2)-set and Yh be a (6h+2)-set. It is clear that GDD(X0,Y0;4,1)=∅.  We now construct a GDD(2,8;4,1), (X0,Y1;ℬ), with X0={x,y}, Y1={a1,a2,…,a8}, A={a1,a2,a3}, Y1′=Y1-A, and ℬ=ℬ1∪ℬ2∪ℬ3∪ℬ4, where ℬ1∈BIBD(A,3,4), ℬ2∈STS(X∪Y1′), ℬ3=⋃i=13(ai+E(K(Y1′))), and ℬ4={{ai,x,y}:i=1,2,3}. We now construct a GDD(6k+2,6h+2;4,1), (Xk,Yh;ℬ), in general case, where k≥0 and h≥1. We first let A={a1,a2,a3}⊆Yh, Yh′=Yh-A, and we will use a result on the existence of GDD(1,6h-1;1,4) which has been shown in Theorem 2.6(f), namely, GDD({a},Yh′;1,4)≠∅. Therefore, we can choose ℬi∈GDD({ai},Yh′;1,4),ℬ4∈BIBD(A,3,4),ℬ5∈STS(Xk∪Yh′), and ℬ6=⋃i=13Fi, where Fi∈STS(Xk∪{ai}). We can see that ℬ∈GDD(Xk,Yh;4,1), where ℬ=ℬ1∪ℬ2∪ℬ3∪ℬ4∪ℬ5∪ℬ6.
Case 2 (6k + 2, 6h + 4).
LetXk be a (6k+2)-set and Yh be a (6h+4)-set. It is easy to see that GDD(X0,Y0;4,1)≠∅ by constructing (X0,Y0;ℬ) as follows. Let X0={a,b}, Y0={1,2,3,4}, and ℬ=⋃i=14{{i,a,b}}∪𝒫2∪𝒫2, where 𝒫2={{1,2,3},{1,2,4},{1,3,4},{2,3,4}}. We now turn to more general cases. Suppose that a∈Yh and Yh′=Yh-{a}.  Since Yh′ is a (6h+3)-set, it follows that KTS(Yh′)≠∅. Choose ℬ1∈KTS(Yh′) with parallel classes 𝒫1,𝒫2,…,𝒫3h+1. Let ℬ2=(a*𝒫1)∪(a*𝒫2)∪(⋃i=33h+1𝒫i). We have shown in Lemma 3.4(d) that GDD(Xk,Yh′;3,1)≠∅. Choose ℬ3∈GDD(Xk,Yh′;3,1) and ℬ4∈STS(Xk∪{a}). We can see that ℬ∈GDD(Xk,Yh;4,1), where ℬ=ℬ2∪ℬ3∪ℬ4.
(d) LetXk be a (6k+6)-set and Yh be a (6h+2)-set. Let X0={a1,a2,…,a6} and Y0={a,b}. Let ℬ1={{ai,a,b}:i=1,2,…,6}, ℬ2∈BIBD(X0,3,6). Then ℬ1∪ℬ2∈GDD(X0,Y0;6,1).
Next we will show that GDD(Xk,Y0;6,1)≠∅ by letting Xk={a1,a2,…,a6k+6}, Y0={a,b}, A={a1,a2,…,a5} and Xk′=Xk-A. Let ℬ1={{ai,a,b}:i=1,2,…,5}, ℬ2∈STS({a,b}∪Xk′), and ℬ3∈BIBD(A,3,6). Theorem 2.6(b) shows an existence of a GDD(1,6h+1;1,6). Let ℬ4=⋃i=15ℬi′, where ℬi′∈GDD({ai},Xk′;1,6). It is easy to check that ℬ∈GDD(Xk,Y0;6,1), where ℬ=ℬ1∪ℬ2∪ℬ3∪ℬ4.
Finally, leth≥1, a∈Y and Yh′=Yh-{a}. We now choose ℬ1∈BIBD(Xk,3,4), ℬ2∈BIBD(Yh′,3,4), ℬ3∈STS(Xk∪Yh′), and ℬ4∈STS(Xk∪{a}). By Theorem 2.6(b) that GDD({a},Yh′;1,6)≠∅. Choose ℬ5∈GDD({a},Yh′;1,6). Thus, we can check that ℬ∈GDD(Xk,Yh;6,1), where ℬ=ℬ1∪ℬ2∪ℬ3∪ℬ4∪ℬ5. Thus (6k+6,6h+2)∈S(6) for all positive integers h,k.Now we have an existence of a GDD(m,n;r,1) for r=1,2,…,6 whenever m and n are not equal to 2,  so we can readily extend to any 6t+r by the following lemma.Lemma 3.6.
Letm and n be positive integers with m≠2 and n≠2. If there exists a  GDD(m,n;r,1) with r≥1, then a  GDD(m,n;6t+r,1),t≥0, existsProof.
LetX be an m-set and Y be an n-set. By assumption we have GDD(X,Y;r,1)≠∅. Choose ℬ1∈GDD(X,Y;r,1). Since m and n are not equal to 2, by Theorem 2.5(a) there exist ℬ2∈BIBD(X,3,6t) and ℬ3∈BIBD(Y,3,6t). It is easy to see that (X,Y;ℬ) forms a GDD(m,n;6t+r,1), where ℬ=ℬ1∪ℬ2∪ℬ3. Thus (m,n)∈S(6t+r) with r≥1.Finally, we have the main result as in the following.Theorem 3.7.
Letm and n be positive integers with m≠2 and n≠2. There exists a  GDD(m,n;λ,1),λ≥1 if and only if
(1)
3∣λ[m(m-1)+n(n-1)]+2mn and(2)
2∣λ(m-1)+n and 2∣λ(n-1)+m.Proof.
The proof follows from Lemmas3.1–3.6.



---

*Source: 148580-2011-07-27.xml*