Packing paths in a $(\lambda +\mu )K_{v+u}-\lambda K_v$

Abstract

Following standard terminology, $\lambda K_v$ is a multigraph on $v$ vertices such that $\lambda$ edges join each pair of vertices. Let $(\lambda +\mu )K_{v+u}-\lambda K_v$ be the graph $(V\cup U,E)$ with $|V|=v$, $|U|=u$, and $(\lambda +\mu )-\lambda =\mu$ edges between the vertices $x$ and $y$ if $x$ and $y$ both lie in $V$ and $\lambda +\mu$ edges between $x$ and $y$ otherwise. The main result of this paper establishes necessary and sufficient conditions for an $m$-path decomposition of $(\lambda +\mu )K_{v+u}-\lambda K_v$.

This paper has been withdrawn due to a crucial error in Theorem 28