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\), \(\deg(v, G_1) = \deg(v, G_2) = \frac{1}{2}\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)| \leq 1\). We show that if \(G\) is a \(\Delta\)-regular multigraph with an even number of vertices and with \(\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.