Jenq-Jong Lin¹, Min-Jen Jou²

Show more
¹ Department of Finance, Ling Tung University, Taiwan.
² Department of Information Technology, Ling Tung University, Taiwan.
Show less

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 H_i, where . Let C_k, P_k and S_k 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 .

Keywords: Balanced Complete Bipartite Multigraph, Cycle, Path, Star, Decomposition

Cite this paper: Lin, J. and Jou, M. (2016) {C_k, P_k, S_k} -Decompositions of Balanced Complete Bipartite Multigraphs. Open Journal of Discrete Mathematics, 6, 174-179. doi: 10.4236/ojdm.2016.63015.

References

[1]   Tazawa, S. (1985) Decomposition of a Complete Multipartite Graph into Isomorphic Claws. SIAM Journal on Algebraic Discrete Methods, 6, 413-417.
http://dx.doi.org/10.1137/0606043

[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 λK_n,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.
http://dx.doi.org/10.1007/s00373-003-0530-3

[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 λK_m 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.
http://dx.doi.org/10.1016/j.disc.2010.04.009

[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.
http://dx.doi.org/10.1007/s00373-011-1105-3

[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.
http://dx.doi.org/10.1155/2013/398473

[17]   Lin, J.J. and Jou, M.J. (2016) {C_k, P_k, S_k}-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 K_m,n (K^*_m,n) into Cycles (Circuits) of Length . Journal of Combinatorial Theory, Series B, 30, 75-81.