Tournaments associated with multigraphs and a theorem of Hakimi |
| |
Authors: | Richard A Brualdi Eliseu Fritscher |
| |
Institution: | 1. Department of Mathematics, University of Wisconsin, Madison, WI 53706, United States;2. Instituto de Matemática, Universidade Federal Do Rio Grande Do Sul, 91509-900 Porto Alegre-RS, Brazil |
| |
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: | Tournament Score vector Multigraph |
本文献已被 ScienceDirect 等数据库收录! |
|