OJDM  Vol.6 No.3 , July 2016
{Ck, Pk, Sk} -Decompositions of Balanced Complete Bipartite Multigraphs
Abstract: Let be a family of subgraphs of a graph G. An L-decomposition of G is an edge-disjoint decomposition of G into positive integer copies of Hi, where . Let Ck, Pk and Sk denote a cycle, a path and a star with k edges, respectively. For an integer , we prove that a balanced complete bipartite multigraph  has a -decomposition if and only if k is even, and .
Cite this paper: Lin, J. and Jou, M. (2016) {Ck, Pk, Sk} -Decompositions of Balanced Complete Bipartite Multigraphs. Open Journal of Discrete Mathematics, 6, 174-179. doi: 10.4236/ojdm.2016.63015.

[1]   Tazawa, S. (1985) Decomposition of a Complete Multipartite Graph into Isomorphic Claws. SIAM Journal on Algebraic Discrete Methods, 6, 413-417.

[2]   Ushio, K., Tazawa, S. and Yamamoto, S. (1978) On Claw-Decomposition of Complete Multipartite Graphs. Hiroshima Mathematical Journal, 8, 207-210.

[3]   Yamamoto, S., Ikeda, H., Shige-Ede, S., Ushio, K. and Hamada, N. (1975) On Claw Decomposition of Complete Graphs and Complete Bipartie Graphs. Hiroshima Mathematical Journal, 5, 33-42.

[4]   Parker, C.A. (1998) Complete Bipartite Graph Path Decompositions. PhD Dissertation, Auburn University, Auburn.

[5]   Shyu, T.W. (2007) Path Decompositions of λKn,n. Ars Combinatoria, 85, 211-219.

[6]   Bryant, D. and Rodger, C.A. (2007) Cycle Decompositions. In: Colbourn, C.J. and Dinitz, J.H., Eds., The CRC Handbook of Combinatorial Designs, 2nd Edition, CRC Press, Boca Raton, 373-382.

[7]   Lindner, C.C. and Rodger, C.A. (1992) Decomposition in Cycles II: Cycle Systems, In: Dinitz, J.H. and Stinson, D.R., Eds., Contemporary Design Theory: A Collection of Surveys, Wiley, New York, 325-369.

[8]   Abueida, A. and Daven, M. (2003) Multidesigns for Graph-Pairs of Order 4 and 5. Graphs and Combinatorics, 19, 433-447.

[9]   Abueida, A. and Daven, M. (2004) Mutidecompositons of the Complete Graph. Ars Combinatoria, 72, 17-22.

[10]   Abueida, A. and O’Neil, T. (2007) Multidecomposition of λKm into Small Cycles and Claws. Bulletin of the Institute of Combinatorics and Its Applications, 49, 32-40.

[11]   Priyadharsini, H.M. and Muthusamy, A. (2009) -Multifactorization of . Journal of Combinatorial Mathematics and Combinatorial Computing, 69, 145-150.

[12]   Shyu, T.W. (2010) Decomposition of Complete Graphs into Paths and Stars. Discrete Mathematics, 310, 2164-2169.

[13]   Shyu, T.W. (2010) Decompositions of Complete Graphs into Paths and Cycles. Ars Combinatoria, 97, 257-270.

[14]   Shyu, T.W. (2013) Decomposition of Complete Graphs into Cycles and Stars. Graphs and Combinatorics, 29, 30-313.

[15]   Lee, H.C. (2013) Multidecompositions of Complete Bipartite Graphs into Cycles and Stars. Ars Combinatoria, 108, 355-364.

[16]   Lee, H.C. and Chu, Y.-P. (2013) Multidecompositions of the Balanced Complete Bipartite Graph into Paths and Stars. ISRN Combinatorics, 2013, Article ID: 398473.

[17]   Lin, J.J. and Jou, M.J. (2016) {Ck, Pk, Sk}-Decompositions of Balanced Complete Bipartite Graphs. (Submitted)

[18]   Lin, C., Lin, J.J. and Shyu, T.W. (1999) Isomorphic Star Decomposition of Multicrowns and the Power of Cycles. Ars Combinatoria, 53, 249-256.

[19]   Sotteau, D. (1981) Decomposition of Km,n (K*m,n) into Cycles (Circuits) of Length . Journal of Combinatorial Theory, Series B, 30, 75-81.