Let $P_k$ and $S_k$ denote a path and a star, respectively, on $k$ vertices. We give necessary and sufficient conditions for the existence of a complete $\{P_5,S_5\}$-decomposition of Cartesian product of complete graphs.

We give necessary and sufficient conditions for the decomposition of complete bipartite multigraph Km,n(λ) into paths and cycles having k edges. In particular, we show that such decomposition exists in Km,n(λ), when λ ≡ 0 (mod 2), [...] and k(p + q) = 2mn for k ≡ 0 (mod 2) and also when λ ≥ 3, λm ≡ λn ≡ 0(mod 2), k(p + q) =λ_mn, m, n ≥ k, (resp., m, n ≥ 3k/2) for k ≡ 0(mod 4) (respectively, for k ≡ 2(mod 4)). In fact, the necessary conditions given above are also sufficient when λ = 2.

R. Frucht and J. Gallian (1988) proved that bipartite prisms of order $2n$ have an $\alpha$-labeling, thus they decompose the complete graph $K_{6nx+1}$ for any positive integer $x$. We use a technique called the ${\rho }^{+}$-labeling introduced by S. I. El-Zanati, C. Vanden Eynden, and N. Punnim (2001) to show that also some other families of 3-regular bipartite graphs of order $2n$ called generalized prisms decompose the complete graph $K_{6nx+1}$ for any positive integer $x$.