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)\ge 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\ge 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$.