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
\(\lambda n^2 \equiv 0 \pmod{k-1}\); and
\(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\).


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