Path Decompositions of $\lambda K_{n,n}$

Abstract

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{G}$ 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(\mathrm{mod}k-1)$ and (ii) $k\le n+1$ if $\lambda =1$ and $n$ is odd, or $k\le 2n$ if $\lambda \ge 2$ or $n$ is even. In this paper, we show these necessary conditions are sufficient except for the possibility of the case that $k=3$, $n=15$, and $k=28$.