On Complete Bipartite Decomposition of Complete Multigraphs

Abstract

Let \(K(n | t)\) denote the complete multigraph containing \(n\) vertices and exactly \(t\) edges between every pair of distinct vertices, and let \(f(m,t)\) be the minimum number of complete bipartite subgraphs into which the edges of \(K(n|t)\) can be decomposed. Pritikin [3] proved that \(f(n;t) \geq \max\{n-1,t\}\), and that \(f(m;2) = n\) if \(n = 2,3,5\), and \(f(m;2) = n-1\), otherwise. In this paper, for \(t \geq 3\) using Hadamard designs, skew-Hadamard matrices and symmetric conference matrices [6], we give some complete multigraph families \(K(n|t)\) with \(f(n;t) = n-1\).