On a Well-Spread Halving of Regular Multigraphs

Abstract

Let $G$ be a connected multigraph with an even number of edges and suppose that the degree of each vertex of $G$ is even. Let $(uv,G)$ denote the multiplicity of edge $(u,v)$ in $G$. It is well known that we can obtain a halving of $G$ into two halves $G_1$ and $G_2$, i.e. that $G$ can be decomposed into multigraphs $G_1$ and $G_2$, where for each vertex $v$, $\mathrm{deg}(v,G_1)=\mathrm{deg}(v,G_2)=\frac{1}{2}\mathrm{deg}(v,G)$. It is also easy to see that if the edges with odd multiplicity in $G$ induce no components with an odd number of edges, then we can obtain such a halving of $G$ into two halves $G_1$ and $G_2$ that is well-spread, i.e. for each edge $(u,v)$ of $G$, $|\mu (uv,G_1)–\mu (uv,G_2)|\le 1$. We show that if $G$ is a $\mathrm{\Delta }$-regular multigraph with an even number of vertices and with $\mathrm{\Delta }$ being even, then even if the edges with odd multiplicity in $G$ induce components with an odd number of edges, we can still obtain a well-spread halving of $G$ provided that we allow the addition/removal of a Hamilton cycle to/from $G$. We give an application of this result to obtaining sports schedules such that multiple encounters between teams are well-spread throughout the season.