 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  10vVGvvmod2 ,10modEGvd12,,,mnn n1mii (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 KXX, where these Xi are disjoint and iiXnGB12,,,mnn nKG12,,,mnn nK12,,,mnn nK1212 rkk krGHDnnn-mGHDn-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 ; When k = 5, J. C. Bermond gives a complete solution in . When G = Sk, Pk and Ck, K. Ushio investigated the exis- tence of G-design of complete multipartite graph in . 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 . 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, nGK (nK be a empty graph with n vertices). Observe that KnnlltK 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 llll, 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.  aced bGraph 1. Let G be a simple graph with five points-six edges. Copyright © 2012 SciRes. APM C. Y. GU, W. ZHOU 302    ,,, ,,, , ,,,aib jckckdiej—1 ,,i jklB YY 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 BBBK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BKBKv N , then is the PBD-closure of K. Lemma 2.2  If K = {3, 4, 5, 6, 8}, then 3n Nn BK . Lemma 2.3  If K = {3, 4, 6}, then  0,1mod 33,BKv Nnn  Lemma 2.4  If K = {5, 9, 13, 17, 29, 33}, then  1mod 4n4,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 Zt 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 AAkK , as there exists a G-HD (tk), let A × Zt be the vertex set of G-HD(tk) and block set be ABBB AB. be a , so (Y, ) be a G-HD(tn). AASimilar 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  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   12:1,3, -,4,0,1,2,3,41,3, -,4,5,6,7,8,9iiiii iiiiii 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 31222 2211 2233221 13322 333331111 111332211222 223 3333321 123132 231213 3:,, -,,,,- ,,,,- ,,,,-,,,,- ,,,,- ,,,,-,,,,- ,,,,-,,,,- ,,,,-,,,, -bca abcacbbaebea abeeda aedcea aceace eadbdaabdcda acdacddabedb bcdedb bcdedb bB12321 132132 213213 321,,,,- ,,,,- ,,,,-, ,cddec cebdec cebdec 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 246,10, 3-3,12,144 mod243,21,2 -2,20,14mod243,7,1-1,9, 234mod 2423,5,18-18,6,164 mod 244,8,1-1,10, 04 mod240,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,12mod2716,23,26-26,25,20mod 27BG 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 515, 29mod514, 32mod510, 33mod 51GZ17}, 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,23,15,0-0, 25,11, 0-0, 21, 10 ,0-0,2B  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,142, 53, 0-0, 2,41,54,0- 0,540, 55, 0-0, 6,39,70,0- 0,7,38, 68, 0-0,8,37,73,0- 0,1B,4mod8727mod 87, 23mod 8726mod8728 mod8724mod 870, 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  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}.  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}.  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.  J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications,” Macmillan Press, London, 1976. 3. G-Designs of Complete Multipartite Graph  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: