Let and denote a path and a star with edges, respectively. For graphs , , and , a -multidecomposition of is a partition of the edge set of into copies of and copies of with at least one copy of and at least one copy of . In this paper, necessary and sufficient conditions for the existence of the ( , )-multidecomposition of the balanced complete bipartite graph are given. 1. Introduction Let , , and be graphs. A -decomposition of is a partition of the edge set of into copies of . If has a -decomposition, we say that is -decomposable and write . A -multidecomposition of is a partition of the edge set of into copies of and copies of with at least one copy of and at least one copy of . If has a -multidecomposition, we say that is -multidecomposable and write . For positive integers and , denotes the complete bipartite graph with parts of sizes and . A complete bipartite graph is balanced if . A -path, denoted by , is a path with edges. A -star, denoted by , is the complete bipartite graph . A -cycle, denoted by , is a cycle of length . -decompositions of graphs have been a popular topic of research in graph theory. Articles of interest include [1–11]. The reader can refer to [12] for an excellent survey of this topic. Decompositions of graphs into -stars have also attracted a fair share of interest. Articles of interest include [13–18]. The study of the -multidecomposition was introduced by Abueida and Daven in [19]. Abueida and Daven [20] investigated the problem of the -multidecomposition of the complete graph . Abueida and Daven [21] investigated the problem of the -multidecomposition of several graph products where denotes two vertex disjoint edges. Abueida and O'Neil [22] settled the existence problem of the -multidecomposition of the complete multigraph for , and . In [23], Priyadharsini and Muthusamy gave necessary and sufficient conditions for the existence of the -multidecomposition of where . Furthermore, Shyu [24] investigated the problem of decomposing into -paths and -stars, and gave a necessary and sufficient condition for . In [25], Shyu considered the existence of a decomposition of into -paths and -cycles and established a necessary and sufficient condition for . He also gave criteria for the existence of a decomposition of into -paths and cycles in [26]. Shyu [27] investigated the problem of decomposing into -cycles and -stars and settled the case . Recently, Lee [28] established necessary and sufficient conditions for the existence of the -multidecomposition of a complete bipartite graph. In this paper, we investigate the problem of the
References
[1]
A. Bouchet and J.-L. Fouquet, “Trois types de décompositions d'un graphe en cha？nes,” Annals of Discrete Mathematics, vol. 17, pp. 131–141, 1983.
[2]
K. Heinrich, J. Liu, and M. Yu, “ -decompositions of regular graphs,” Journal of Graph Theory, vol. 31, no. 2, pp. 135–143, 1999.
[3]
M. S. Jacobson, M. Truszczyński, and Z. Tuza, “Decompositions of regular bipartite graphs,” Discrete Mathematics, vol. 89, no. 1, pp. 17–27, 1991.
[4]
A. Kotzig, “From the theory of finite regular graphs of degree three and four,” ？asopis pro pěstování matematiky, vol. 82, pp. 76–92, 1957.
[5]
C. S. Kumar, “On -decomposition of graphs,” Taiwanese Journal of Mathematics, vol. 7, no. 4, pp. 657–664, 2003.
[6]
H.-C. Lee, M.-J. Lee, and C. Lin, “Isomorphic path decompositions of for odd ,” Taiwanese Journal of Mathematics, vol. 13, no. 2A, pp. 393–402, 2009.
[7]
C. A. Parker, Complete bipartite graph path decompositions [Ph.D. thesis], Auburn University, Auburn, Ala, USA, 1998.
[8]
T.-W. Shyu, “Path decompositions of ,” Ars Combinatoria, vol. 85, pp. 211–219, 2007.
[9]
T.-W. Shyu and C. Lin, “Isomorphic path decompositions of crowns,” Ars Combinatoria, vol. 67, pp. 97–103, 2003.
[10]
M. Tarsi, “Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs,” Journal of Combinatorial Theory A, vol. 34, no. 1, pp. 60–70, 1983.
[11]
M. Truszczyński, “Note on the decomposition of into paths,” Discrete Mathematics, vol. 55, no. 1, pp. 89–96, 1985.
[12]
K. Heinrich, “Path-decompositions,” Le Matematiche, vol. 47, no. 2, pp. 241–258, 1992.
[13]
D. E. Bryant, S. El-Zanati, C. V. Eynden, and D. G. Hoffman, “Star decompositions of cubes,” Graphs and Combinatorics, vol. 17, no. 1, pp. 55–59, 2001.
[14]
C. Lin, J.-J. Lin, and T.-W. Shyu, “Isomorphic star decompositions of multicrowns and the power of cycles,” Ars Combinatoria, vol. 53, pp. 249–256, 1999.
[15]
M. Tarsi, “Decomposition of complete multigraphs into stars,” Discrete Mathematics, vol. 26, no. 3, pp. 273–278, 1979.
[16]
S. Tazawa, “Decomposition of a complete multipartite graph into isomorphic claws,” Society for Industrial and Applied Mathematics, vol. 6, no. 3, pp. 413–417, 1985.
[17]
K. Ushio, S. Tazawa, and S. Yamamoto, “On claw-decomposition of a complete multipartite graph,” Hiroshima Mathematical Journal, vol. 8, no. 1, pp. 207–210, 1978.
[18]
S. Yamamoto, H. Ikeda, S. Shige-eda, K. Ushio, and N. Hamada, “On claw-decomposition of complete graphs and complete bigraphs,” Hiroshima Mathematical Journal, vol. 5, pp. 33–42, 1975.
[19]
A. Abueida and M. Daven, “Multidesigns for graph-pairs of order 4 and 5,” Graphs and Combinatorics, vol. 19, no. 4, pp. 433–447, 2003.
[20]
A. Abueida and M. Daven, “Multidecompositions of the complete graph,” Ars Combinatoria, vol. 72, pp. 17–22, 2004.
[21]
A. Abueida and M. Daven, “Multidecompositions of several graph products,” Graphs and Combinatorics, 2012.
[22]
A. Abueida and T. O'Neil, “Multidecomposition of into small cycles and claws,” Bulletin of the Institute of Combinatorics and its Applications, vol. 49, pp. 32–40, 2007.
[23]
H. M. Priyadharsini and A. Muthusamy, “ -multifactorization of ,” Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 69, pp. 145–150, 2009.
[24]
T.-W. Shyu, “Decomposition of complete graphs into paths and stars,” Discrete Mathematics, vol. 310, no. 15-16, pp. 2164–2169, 2010.
[25]
T.-W. Shyu, “Decompositions of complete graphs into paths and cycles,” Ars Combinatoria, vol. 97, pp. 257–270, 2010.
[26]
T. W. Shyu, “Decomposition of complete graphs into paths of length three and triangles,” Ars Combinatoria, vol. 107, pp. 209–224, 2012.
[27]
T.-W. Shyu, “Decomposition of complete graphs into cycles and stars,” Graphs and Combinatorics, 2011.
[28]
H.-C. Lee, “Multidecompositions of complete bipartite graphs into cycles and stars,” Ars Combinatoria, vol. 108, pp. 355–364, 2013.
