Advances in Pure Mathematics, 2012, 2, 301303 http://dx.doi.org/10.4236/apm.2012.24040 Published Online July 2012 (http://www.SciRP.org/journal/apm) GDesign of Complete Multipartite Graph Where G Is Five PointsSix 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 Gdesigns of complete multipartite graph, where G is five pointssix 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 Gdesign (or Gdecomposition) 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 Gdesign is denoted by GGD(v). Obviously, the necessary conditions for the existence of a GGD(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 , where these Xi are disjoint and ii 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 Gdesign, 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 Gdesign is denoted by . When n1 = n2 = ··· = nm = n, the holey Gdesign is de noted by (also known as Gdecomposition of complete multipartite graph Kn(t)). On the Gdesign 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 Gdesign of complete multipartite graph in [3]. In this paper, Gdesigns of complete multipartite graph, where G is five pointssix edges is studied. Necessary and sufficient conditions are given for the Gdesigns 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 pointssix 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 be a empty graph with n vertices). Observe that nnl ltK tK. Lemma 2.1. If there exists a GHD(tn), then there ex ists a GHD((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 pointssix 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 PBDclosure 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 GHD(tk) where k {3, 4, 5, 6, 8}, then there exists a GHD(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 kK , as there exists a GHD (tk), let A × Zt be the vertex set of GHD(tk) and block set be B BB AB . be a , so (Y, ) be a GHD(tn). A A Similar to the proof of lemma 2.5, We have the fol lowing conclusions. Lemma 2.6 If there exists a GHD(tk) for k {3, 4, 6}, then there exists a GHD(tn) for n ≡ 0, 1 (mod 3) and n > 3. Lemma 2.7 If there exists a GHD(tk) for k {5, 9, 13, 17, 29, 33}, then there exists a GHD(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 GHD(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 GHD(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 GHD(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 GHD(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 GHD(38). Proof. Take X = Z24 and G = {{i, i + 8, i + 16}, i Z8}, we list vertex set and blocks below :5,9, 22,11,134 mod 24 6,10, 33,12,144 mod24 3,21,2 2,20,14mod24 3,7,11,9, 234mod 24 23,5,1818,6,164 mod 24 4,8,11,10, 04 mod24 0,6,1919, 7,174mod 24 B Lemma 2.14 There exists a GHD(39). Proof. Take X = Z27 and G = {{i, i + 9, i + 18}, i Z9}, we list vertex set and blocks below :2,13, 00,4,12mod27 16,23,2626,25,20mod 27 B G Lemma 2.15 There exists a GHD(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,00, 2 5,11, 00, 2 1, 10 ,00,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 GHD(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,00,1 42, 53, 00, 2, 41,54,0 0,5 40, 55, 00, 6, 39,70,0 0,7, 38, 68, 00,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, “GDecomposition of Kn, Where G Has Four Vertices or Less,” Discrete Mathematics, Vol. 19, No. 2, 1997, pp. 113120. doi:10.1016/0012365X(77)900279 Lemma 2.17 There exists a GHD(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. 293318. 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 GHD(3k), for k {13, 33}. [3] K. Ushio, “GDesigns and Related Designs,” Discrete Mathematics, Vol. 116, No. 13, 1993, pp. 299311. doi:10.1016/0012365X(93)90408L 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. GDesigns 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 GHD(tn) are sufficient for the following n and t:
