%0 Journal Article
%T Multidecompositions of the Balanced Complete Bipartite Graph into Paths and Stars
%A Hung-Chih Lee
%A Yen-Po Chu
%J ISRN Combinatorics
%D 2013
%R 10.1155/2013/398473
%X 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¨C11]. 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¨C18]. 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
%U http://www.hindawi.com/journals/isrn.combinatorics/2013/398473/