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 \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 these necessary conditions are sufficient except for the possibility of the case that \(k=3\), \(n=15\), and \(k=28\).