Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647236 | Discrete Mathematics | 2015 | 7 Pages |
Abstract
A tournament of order n is usually considered as an orientation of the complete graph Kn. In this note, we consider a more general definition of a tournament that we call aC-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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Richard A. Brualdi, Eliseu Fritscher,