Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n is usually considered as an orientation of the complete graph K. In this note, we consider a more general definition of a tournament that we call a C-tournament, where C is the adjacency matrix of a multigraph G, and a C-tournament is an orientation of G. The score vector of a C-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C-tournament with a prescribed score vector R and gave an algorithm to construct such a C-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi's theorem, and then provide a direct construction of such a C-tournament which works even for weighted graphs. (C) 2014 Elsevier B.V. All rights reserved.