Advances in Pure Mathematics, 2012, 2, 301-303
http://dx.doi.org/10.4236/apm.2012.24040 Published Online July 2012 (http://www.SciRP.org/journal/apm)
G-Design of Complete Multipartite Graph Where G Is
Five Points-Six Edges
Chengyang Gu, Wei Zhou
School of Mathematical Sciences, Huaiyin Normal University, Huai’an, China
Email: gcy1964@sina.com, gcy@hytc.edu.cn
Received March 3, 2012; revised April 27, 2012; accepted May 5, 2012
ABSTRACT
In this paper, we construct G-designs of complete multipartite graph, where G is five points-six edges.
Keywords: Complete Multipartite Graph; Graph Design; Latin Square
1. Introduction
Let Kv be a complete graph with v vertices, and G be a
simple graph with no isolated vertex. A G-design (or
G-decomposition) is a pair (X, B), where X is the vertex
set of Kv and B is a collection of subgraphs of Kv, called
blocks, such that each block is isomorphic to G and any
edge of Kv occurs in exactly a blocks of B. For simplicity,
such a G-design is denoted by G-GD(v). Obviously, the
necessary conditions for the existence of a G-GD(v) are

 
10
vVG
vv
mod2 ,
10mod
EG
vd
12
,,,
m
nn n
1
m
i
i
(1)
where d is the greatest common divisor of the degrees of
the vertices in V(G).
Let be a complete multipartite graph with
vertex set
K
X
X
, where these Xi are disjoint and
ii
X
n
GB
12
,,,
m
nn n
KG
12
,,,
m
nn n
K
12
,,,
m
nn n
K

12
12 r
kk k
r
GHDnnn-

m
GHDn-
GG
, 1 i m. For a given graph G, a holey
G-design, denoted by (X, , ), where X is the vertex set
of , ={X1, X2, ···, Xm} (Xi called hole) and B
is a collection of subgraphs of called blocks,
such that each block is isomorphic to G and any edge of
occurs in exactly a blocks of B. When the
multipartite graph has ki partite of size ni 1 i r, the
holey G-design is denoted by .
When n1 = n2 = ··· = nm = n, the holey G-design is de-
noted by (also known as G-decomposition
of complete multipartite graph Kn(t)).
On the G-design of existence has a lot of research. Let
k be the vertex number of G, When k 4, J. C. Bermond
proved that condition (1) is also sufficient in [1]; When k
= 5, J. C. Bermond gives a complete solution in [2].
When G = Sk, Pk and Ck, K. Ushio investigated the exis-
tence of G-design of complete multipartite graph in [3].
In this paper, G-designs of complete multipartite graph,
where G is five points-six edges is studied. Necessary
and sufficient conditions are given for the G-designs of
complete multipartite graph Kn(t). For graph theoretical
term, see [4].
2. Fundamental Theorem and Some Direct
Construction
Let G be a simple graph with five points-six edges (see
Graph 1). G is denoted by (a, b, c)-(c, d, e).
The lexicographic product 12
of the graphs G1
and G2 is the graph with vertex set V(G1) × V(G2) and an
edge joining (u1, u2) to (v1, v2) if and only if either u1 is
adjacent to v1 in G1 or u1 = v1 and u2 and v2 are adjacent
in G2. We are only concered with a particular kind of
lexicographic product, n
GK
(n
K
be a empty graph
with n vertices). Observe that

K
nnl
ltK tK.
Lemma 2.1. If there exists a G-HD(tn), then there ex-
ists a G-HD((lt)n) for any integer l.
Proof. Let
1, 2,,VK lll
l, Take any
latin
square and consider each element in the form
,,

where
denotes the row,
the column and
the
entry, with 1,,l

. We can construct l2 graphs G.
a
c
e
d
b
Graph 1. Let G be a simple graph with five points-six edges.
C
opyright © 2012 SciRes. APM
C. Y. GU, W. ZHOU
302
  


 

,,, ,,, , ,,,aib jckckdiej

1 ,,i jkl
B Y
Y
Let K be a subset of positive integers. A pairwise bal-
anced design (PBD(v, K)) of order v with block sizes
from K is a pair (Y, ),where is a finite set (the
point set) of cardinality v and B is a family of subsets
(blocks) of which satisfy the properties:
1) If , then
BBBK
B
.
2) Every pair of distinct elements of Y occurs in ex-
actly a blocks of .
Let K be a set of positive integers and
 

,PBDvK

BK
BKv N ,
then is the PBD-closure of K.
Lemma 2.2 [5] If K = {3, 4, 5, 6, 8}, then


3n Nn BK .
Lemma 2.3 [5] If K = {3, 4, 6}, then
 

0,1mod 33,BKv Nnn 
Lemma 2.4 [5] If K = {5, 9, 13, 17, 29, 33}, then
 

1mod 4n4,BKv Nn
Lemma 2.5 If there exists a G-HD(tk) where k
{3, 4,
5, 6, 8}, then there exists a G-HD(tn) where n 3.
Proof. Let X be n(n 3) element set and Z
t be a
modulo t residual additive group. For K = {3, 4, 5, 6, 8},
take Y = X × Zt, by applying Lemma 2.2, we assume that
(X, ) be a PBD(n, k). In the A, we take a block A, for A
A
kK , as there exists a G-HD (tk), let A × Zt be the
vertex set of G-HD(tk) and block set be
A
B

BB AB
. be a
, so (Y, ) be a G-HD(tn).
A
A
Similar to the proof of lemma 2.5, We have the fol-
lowing conclusions.
Lemma 2.6 If there exists a G-HD(tk) for k
{3, 4,
6}, then there exists a G-HD(tn) for n 0, 1 (mod 3) and
n > 3.
Lemma 2.7 If there exists a G-HD(tk) for k
{5, 9,
13, 17, 29, 33}, then there exists a G-HD(tn) for n 1
(mod 4) and n > 4.
Lemma 2.8 [2] For n 1, 9 (mod 12), there exists a
(n, G, 1)-GD.
Lemma 2.9 There exists a G-HD(23).
Proof. Take X = {a, b, c, d, e, f} and G = {{a, b}, {c, d},
{e, f}}, we list vertex set and blocks below.

 
,,-,,e ebd
,4 2mod4
1
:,,- ,,adff cbcaB
Lemma 2.10 There exists a G-HD(24).
Proof. Take X = Z8 and G = {{0, 4}, {1, 5}, {2, 6},
{3, 7}}, we list vertex set and blocks below

:3,0,1- 1,2B
Lemma 2.11 There exists a G-HD(26).
Proof. Take X = Z12, and G = {{0, 5}, {1, 6}, {2, 7},
{3, 8}, {4, 9}, {
, 2
}}, we list vertex set and blocks
below
 
 
1
2
:1,3, -,4,0,1,2,3,4
1,3, -,4,5,6,7,8,9
iiiii i
iiiii i


B
Lemma 2.12 There exists a G-HD(35).
Proof. Take X = {ai, bi, ci, di, ei}, X1 = {ai} X2 = {bi}
X3 = {ci} X4 = {di} X5 = {ei} (i = 1, 2, 3), and G ={X1, X2,
X3, X4, X5}, we list vertex set and blocks below









 
 




11 113 3
1222 22
11 2233
221 133
22 3333
31111 1
113322
11222 2
23 3333
321 123
132 231
213 3
:,, -,,
,,- ,,
,,- ,,
,,-,,
,,- ,,
,,- ,,
,,-,,
,,- ,,
,,-,,
,,- ,,
,,-,,
,, -
bca abc
acbbae
bea abe
eda aed
cea ace
ace ead
bdaabd
cda acd
acddab
edb bcd
edb bcd
edb b
B




12
321 132
132 213
213 321
,,
,,- ,,
,,- ,,
,,-, ,
cd
dec ceb
dec ceb
dec ceb
Lemma 2.13 There exists a G-HD(38).
Proof. Take X = Z24 and G = {{i, i + 8, i + 16}, i
Z8},
we list vertex set and blocks below
 

 

 

:5,9, 2-2,11,134 mod 24
6,10, 3-3,12,144 mod24
3,21,2 -2,20,14mod24
3,7,1-1,9, 234mod 24
23,5,18-18,6,164 mod 24
4,8,1-1,10, 04 mod24
0,6,19-19, 7,174mod 24
B
Lemma 2.14 There exists a G-HD(39).
Proof. Take X = Z27 and G = {{i, i + 9, i + 18}, i
Z9}, we list vertex set and blocks below
 
:2,13, 0-0,4,12mod27
16,23,26-26,25,20mod 27
B
G
Lemma 2.15 There exists a G-HD(317).
Proof. Take X = Z51 and ={{i, i + 17, i + 34}, i
Copyright © 2012 SciRes. APM
C. Y. GU, W. ZHOU
Copyright © 2012 SciRes. APM
303
3,30mod 51
5, 29mod51
4, 32mod51
0, 33mod 51
G
Z17}, we list vertex set and blocks below 1) t 0 (mod 6) and n 3;
0 (mod 3) and n 0, 1 (mod 3), 2) t 0 (mod 2), t




:2,16,0 - 0,2
3,15,0-0, 2
5,11, 0-0, 2
1, 10 ,0-0,2
B
0 (mod 2) and n 1 (mod 4), 3) t 0 (mod 3), t
0 (mod 2), t
0 (mod 3) and n 1, 9 (mod 12). 4) t
Proof. Necessary conditions are obviously, we prove
the sufficient conditions.
1) For t 0 (mod 6) and n 3, by applying Lemma
2.17 and 2.5.,
Lemma 2.16 There exists a G-HD(329).
2) For t 0 (mod 2), t
0 (mod 3) and n 0, 1 (mod 3)
by applying Lemma 2.9, 2.10, 2.11 and 2.6.
Proof. Take X = Z87 and = {{i, i + 29, i + 58}, i
Z29}, we list vertex set and blocks below
3) For t 0 (mod 3), t
0 (mod 2) and n 1 (mod 4)
by applying Lemma 2.12, 2.14, 2.15, 2.16, 2.18 and 2.7.







:43,52,0-0,1
42, 53, 0-0, 2,
41,54,0- 0,5
40, 55, 0-0, 6,
39,70,0- 0,7,
38, 68, 0-0,8,
37,73,0- 0,1
B







,4mod87
27mod 87
, 23mod 87
26mod87
28 mod87
24mod 87
0, 22mod 87
4) For t
0 (mod 2), t 0 (mod 3) and n 1, 9
(mod 12), by applying Lemma 2.1 and 2.8.
REFERENCES
[1] J. C. Bermond and M. J Schonhei, “G-Decomposition of
Kn, Where G Has Four Vertices or Less,” Discrete
Mathematics, Vol. 19, No. 2, 1997, pp. 113-120.
doi:10.1016/0012-365X(77)90027-9
Lemma 2.17 There exists a G-HD(6k), for k
{3, 4,
5, 6, 8}.
[2] J. C. Bermond, C. Huang, A. Rosa, et al., “Decomposi-
tion of Complete Graphs into Isomorphic Sutgraphs with
Five Vertices,” Ars Combinatoria, Vol. 10, 1980, pp.
293-318.
Proof. By applying Lemma 2.9, 2.10, 2.11, 2.12, 2.13
and 2.1, we can obtain the result.
Lemma 2.18 There exists a G-HD(3k), for k
{13,
33}.
[3] K. Ushio, “G-Designs and Related Designs,” Discrete
Mathematics, Vol. 116, No. 1-3, 1993, pp. 299-311.
doi:10.1016/0012-365X(93)90408-L
Proof. By applying Lemma 2.8 and 2.1, we can obtain
the result. [4] J. A. Bondy and U. S. R. Murty, “Graph Theory with
Applications,” Macmillan Press, London, 1976.
3. G-Designs of Complete Multipartite
Graph [5] C. J. Colbourn and J. H. Dinitz, “The CRC Handbook of
Combinatorial Designs,” CRC Press Inc., Boca Raton,
1996. doi:10.1201/9781420049954
Theorem 3.1 The necessary conditions for the existence
of a G-HD(tn) are sufficient for the following n and t: