×

Multidecompositions of complete bipartite graphs into cycles and stars. (English) Zbl 1289.05375

Summary: Let \(C_k\) denote a cycle of length \(k\) and let \(S_k\) denote a star with \(k\) edges. For graphs \(F\), \(G\) and \(H\), a \((G,H)\)-multidecomposition of \(F\) is a partition of the edge set of \(F\) into copies of \(G\) and copies of \(H\) with at least one copy of \(G\) and at least one copy of \(H\). In this paper, necessary and sufficient conditions for the existence of the \((C_k, S_k)\)-multidecomposition of a complete bipartite graph are given.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite