# zbMATH — the first resource for mathematics

Path decompositions of $$\lambda K_{n,n}$$. (English) Zbl 1224.05264
Summary: Let $$P_k$$ denote a path with $$k$$ vertices and $$k-1$$ edges and let $$\lambda K_{n,n}$$ denote the $$\lambda$$-fold complete bipartite graph with both parts of size $$n$$. A $$P_k$$-decomposition $$\mathcal D$$ of $$\lambda K_{n,n}$$ is a family of subgraphs of $$\lambda K_{n,n}$$ whose edge sets form a partition of the edge set of $$\lambda K_{n,n}$$ such that each member of $$\mathcal D$$ is isomorphic to $$P_k$$. Necessary conditions for the existence of a $$P_k$$-decomposition of $$\lambda K_{n,n}$$ are
(i)
$$\lambda n^2 \equiv 0 \pmod{k-1}$$; and
(ii)
$$k\leq n+1$$ if $$\lambda = 1$$ and $$n$$ is odd, or $$k\leq 2n$$ if $$\lambda \geq 2$$ or $$n$$ is even.
In this paper, we show that these necessary conditions are sufficient except possibly the case that $$\lambda = 3$$, $$n = 15$$ and $$k = 28$$.

##### MSC:
 05C38 Paths and cycles 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
##### Keywords:
$$P_k$$-decomposition; graph